andycode 巨神会莫比乌斯反演!于是我开始严肃学习数学。
这里主要是重要结论。
欧拉函数(\(\phi\))
定义 & 性质
欧拉函数 \(\phi(x)\) 表示不大于 \(x\) 的正整数中与 \(x\) 互质的数的数量。
那质数 \(x\) 的 \(\phi\) 值就是 \(x-1\)。
欧拉函数是积性函数,对于 \(x,y\in \N_+\) 且 \(\gcd(x,y)=1\) 有 \(\phi(xy)=\phi(x)\times \phi(y)\)。
基于此可以用欧拉筛线性求 \(\phi\)。
欧拉筛很好用,可以搭配莫比乌斯反演和数论分块一起食用。
求法
线性求 $\N_+$ 范围内所有数的 $\phi$
void get_phi() {phi[1] = 1; for(int i = 2; i <= N; i++) {if(!npr[i]) prime[++tot] = i, phi[i] = i - 1, vis[i] = i; for(int j = 1; j <= tot && prime[j] * i <= n; j++) {npr[i * prime[j]] = 1; vis[i * prime[j]] = prime[j]; if(i % prime[j] == 0) {phi[i * prime[j]] = phi[i] * prime[j]; break; } phi[i * prime[j]] = phi[i] * phi[prime[j]]; }}
}
如果只求一个数的 \(\phi\) 有更好的求法,需要用到 Pollard-Rho 算法。