莫比乌斯函数模板
如题= =自用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
可巧用在容斥中
函数定义:
对任意k,μ(k) = 0,k是完全平方数的倍数
             = (-1)^(n) , k = p1×p2×p3×...×pn ,p是素数
			 即n的个数是奇数时 为-1
			   n的个数是偶数时 为1
我们又知道对素数进行容斥的话:
ans = +[k=一个素数之积 时对答案的贡献]
	  -[k=两个素数之积 时对答案的贡献]
	  +[k=三个素数之积 时对答案的贡献]
显然完全平方数时贡献是零 奇数,偶数时是系数是莫比乌斯函数的相反数 这样扫一遍就知道容斥的结果了
*/
static int[]prime=new int[100050];
static boolean[]notp=new boolean[100050];
static int[]mu=new int[100050];
static void makeMobius() {
		Arrays.fill(notp, false);
		mu[1] = 1;
		int pnum=0;
		for (int i = 2; i < 100010; i++) {
			if (!notp[i]) {
				prime[++pnum] = i; mu[i] = -1;
			}
			for (int j = 1; prime[j]*i < 100010; j++) {
				notp[prime[j]*i] = true;
				if (i%prime[j] == 0) {
					mu[prime[j]*i] = 0;
					break;
				}
				mu[prime[j]*i] = -mu[i];
			}
		}
	}