仓促之下赶出来的笔记，以后再补充吧

欧拉函数

定义：

小于等于$x$中与$x$互质的数的个数，记作$\phi(x)$

（1与任何数互质）

特别的，$\phi(1)=1$

性质

1. 欧拉函数为积性函数

   即对于互质的整数$a,b$，有$\phi(ab)=\phi(a)\phi(b)$

2. $\sum_{d\mid n} \phi(d)=n$

3. $[1,n]$中与$n$互质的数的和为$n\times \frac{\phi(n)}{2}(n\gt 1)$

   证明：若$gcd(n,i)=1$，则$gcd(n,n-i)=1$，这样的数成对出现且和为$n$

4. $a^{\phi(n)}\equiv 1\mod n$

求法

计算单个数的欧拉函数

复杂度$O(\sqrt{n})$

假设$n$为合数

当$n$为某一质数的幂，即$n=p^x$（$p$为质数）时，有$\phi(n)=p^x-p^{x-1}$

否则，有

$$\begin{aligned}\phi(n)&=\phi(p_1^{x_1}p_2^{x_2}\cdots p_y^{x_k})\\&=\prod_{i=1}^k(p_i^{x_i}-p^{x_i-1})\\&=\prod_{i=1}^k p_i^{x_i-1}(p_i-1) \\&=n\prod_{i=1}^k(1-\frac{1}{p_i})\end{aligned}$$

int GetPhi(int p) {
    int ans = 1;
    for(int i = 2; i * i <= p; i++) {
        if(p % i == 0) {
            int now = i - 1; p /= i;
            while(p % i == 0) now = now * i, p /= i;
            ans = ans * now;
        }
    }
    if(p != 1) ans *= (p - 1); 
    return ans;
}

线性筛

1. 若$p$为素数，$\phi(p)=p-1$

2. 若$n \mod p \not= 0$，且$p$为素数，

   $\phi(np)=\phi(n)\phi(p)=\phi(n)(p-1)$

3. 若$n \mod p =0$，且$p$为素数

   $\phi(np)=\phi(n)*p$

const int maxn = 1e5 + 1001;
int phi[maxn], prime[maxn], pcnt = 0;
bool not_prime[maxn];
void init(int n){
    not_prime[1] = true; 
    for(int i=2; i<=n; i++){
        if(!not_prime[i]) {
            prime[pcnt++] = i;
            phi[i] = i - 1;
        }
        for(int j=0; j<pcnt && i * prime[j] <= n; j++){
            not_prime[i * prime[j]] = true;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}