NOIP模板复习 _ 线性筛(质数/欧拉函数/莫比乌斯函数) – [模板]

#include 
const int N = 10000000;
bool vis[N];
int pr[N], phi[N], mu[N];
void init() {
    mu[1] = phi[1] = 1;
    for(int i = 2; i < N; i ++ ) {
        if(!vis[i]) pr[++*pr] = i, phi[i] = i-1, mu[i] = -1;
        for(int j = 1; j <= *pr && i*pr[j] < N; j ++ ) {
            vis[i*pr[j]] = 1;
            if(i%pr[j]) {
                phi[i*pr[j]] = phi[i]*pr[j];
                break;
            }
            mu[i*pr[j]] = -mu[i];
            phi[i*pr[j]] = phi[i]*phi[pr[j]];
        }
    }
}
int main() {
    init();
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注