欧拉函数

说明

欧拉函数:求从1到p-1中与p互质的数字个数

应用

ab%p = a phi(p)+b%phi(b)%p

欧拉函数

使用方法

  • ll ans = euler(x); 计算x的欧拉函数值

模版

ll euler(ll x) {
    ll res = x;
    for (ll i = 2; i <= x / i; i++)
        if (x % i == 0) {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

欧拉函数值表

说明

计算1-n所有数的欧拉phi函数值

时间复杂度O(nloglongn)

模版

void phi_table(int n,int *phi)  
{  
    //memset(phi,0,sizeof(phi));  //指针不能用这个初始化   
    for(int i=2;i<=n;i++)  phi[i]=0;  
    phi[1]=1;  
    for(int i=2;i<=n;i++)  
    {  
        if(!phi[i])   
        for(int j=i;j<=n;j+=i)  
        {  
            if(!phi[j])  phi[j]=j;  
            phi[j]=phi[j]/i*(i-1);  
        }  
    }   
}

results matching ""

    No results matching ""