2013-team4/code/euler-function

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//复杂度O(sqrt(x)),欧拉函数φ(x)为1到x中与x互质数的个数。φ(1)=1
int euler(int x)
{
    int res = x;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0){
            res -= res / i;
            while(x % i == 0)x /= i;
        }
    }
    if(x > 1)res -= res / x;
    return res;
}
}}}
{{{
//筛法，求MAXN以内的欧拉函数，O(nlogn)
#define MAXN 100020
int f[MAXN];
bool vis[MAXN];
void init_euler(){
    for(int i = 0; i < MAXN; i++)f[i] = i;
    for(int i = 2; i < MAXN; i++){
        if(!vis[i]){
            for(int j = i; j < MAXN; j+=i){
                f[j] -= f[j] / i;
                vis[j] = true;
            }
        }
    }
}
}}}

//复杂度O(sqrt(x)),欧拉函数φ(x)为1到x中与x互质数的个数。φ(1)=1
int euler(int x)
{
    int res = x;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0){
            res -= res / i;
            while(x % i == 0)x /= i;
        }
    }
    if(x > 1)res -= res / x;
    return res;
}

//筛法，求MAXN以内的欧拉函数，O(nlogn)
#define MAXN 100020
int f[MAXN];
bool vis[MAXN];
void init_euler(){
    for(int i = 0; i < MAXN; i++)f[i] = i;
    for(int i = 2; i < MAXN; i++){
        if(!vis[i]){
            for(int j = i; j < MAXN; j+=i){
                f[j] -= f[j] / i;
                vis[j] = true;
            }
        }
    }
}