[数论] 欧拉函数

对于一个正整数 $n$ ,其的欧拉函数即为小于 $n$ 的正整数中与 $n$ 互质的数的数目

欧拉函数是积性函数，可以使用欧拉筛线性筛得。

int phi[MAXN],p[MAXN];
bool prime[MAXN]; 
int cnt;

void get_phi(){
    for(int i=2;i<=MAXN;i++){
        if(!prime[i]){
            p[++cnt] = i;
            phi[i] = i-1;   
        }

        for(int j=1;j<=cnt;j++){
            if(i*p[j] > MAXN)
                break;

            prime[i*p[j]] = true;

            if(i%p[j] == 0){
                phi[i*p[j]] = phi[i] * p[j];
                break;
            }else
                phi[i*p[j]] = phi[i] * (p[j]-1);
        }
    }
}