You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

欧拉函数

. 1 min read

欧拉函数的两种基本写法
欧拉函数有直接求法和打欧拉函数表法。
欧拉函数的定义:对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4,因为1,3,5,7均和8互质。
Euler函数表达通式:
$$ euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn) $$
,其中$-p1,p2……pn-$为x的所有素因数,x是不为0的整数。
$-euler(1)=1-$(唯一和1互质的数就是1本身)。

直接求法:

long long phi(long long x)
{
    int res = x,a = x;
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            res = res/i*(i-1);//res -= res/i;
            while(a%i==0)a/=i;
        }
    }
    if(a>1)res =res/a*(a-1);//res -= res/a;
    return res;

打表大法

#define Max 1000001
int euler[Max];
int main(){
     euler[1]=1;
     for(int i=2;i<Max;i++)
       euler[i]=i;
     for(int i=2;i<Max;i++)
        if(euler[i]==i)
           for(int j=i;j<Max;j+=i)
              euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}


本站总访问量