求一个极大数的欧拉函数 phi(i)

时间：2021-09-08 17:46:15

思路：

　　因为当n>=1e10的时候，线性筛就不好使啦。所以要用一个公式

　　φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)

　　证明详见：《公式证明：欧拉函数》

　　Miller-Rabin算法：

　　　　判断某个数是否是素数，不是素数则返回一个因子。

　　Pollard-Rho算法：

　　　　利用Miller-Rabin求出 质因数。

　　　　具体的：

　　　　　　如果当前的数不是质数，找质因数 再搜Rho(n/d)和Rho(d)

　　　　　　如果是质数（不一定准确），再去判断。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 #include<vector>

 #include<map>

 #include<string>

 #include<iomanip>

 #include<iostream>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define ALL(x,S) for(x=S.begin();x!=S.end();x++)

 typedef long long LL;

 typedef long double real;

 bool pd_prime[];

 set<LL> S;

 set<LL>::iterator pos;

 LL n;

 void prepare()

 {

     int i,j;

     memset(pd_prime,,sizeof pd_prime);

     pd_prime[]=;

     for(int i=;i<=;i++)

     if(pd_prime[i])

     for(int j=;j<=/i;j++)

     pd_prime[i*j]=;

 }

 void addp(LL t)

 { S.insert(t);}

 LL gcd(LL a,LL b)

 {

     if(!b) return a;

     return gcd(b,a%b);

 }

 LL mul(LL a,LL b,LL mod)

 {

     LL ans=;

     while(b)

     {

         if(b&)    ans=(ans+a)%mod;

         a=(a+a)%mod;

         b>>=;

     }

     return ans;

 }

 LL pow(LL a,LL b,LL mod)

 {

     LL ans=;

     while(b)

     {

         if(b&)    ans=mul(ans,a,mod);

         b>>=;

         a=mul(a,a,mod);

     }

     return ans;

 }

 bool MR(LL n,LL k)

 {

     LL s=n-,w=;

     while(!(s&))

         w++,s>>=;

     LL y=pow(k,s,n);

     if(y== || y==n-)

         return ;

     while(w--)

     {

         y=mul(y,y,n);

         if(y==n-)

             return ;

     }

     return ;

 }

 bool prime(LL n)

 {

     if(n<=)

         return pd_prime[n];

     bool flag=;

     for(int i=;i<=;i++)

     if(pd_prime[i])

     if(!MR(n,i))    flag=;

     return flag;

 }

 void rho(LL n)

 {

     if(n==)    return ;

     if(n==)

     {

         addp();

         addp();

         return ;

     }

     if(prime(n))

     {

         addp(n);

         return ;

     }

     LL x,y,d,p;

     while()

     {

         x=,y=,d=;

         p=mul(rand(),rand(),);

         if(d==)

         {

             x=(mul(x,x,n)+p)%n;

             y=(mul(y,y,n)+p)%n;

             y=(mul(y,y,n)+p)%n;

             d=gcd(abs(x-y),n);

         }

         if(d==n)    continue;

         rho(d);rho(n/d);

         return ;

     }

 }

 LL phi(LL x)

 {

     S.clear();

     rho(x);

     LL ans=x;

     ALL(pos,S)

             ans=ans/(*pos)*((*pos)-);

     return ans;

 }

 int main()

 {

     freopen("phi.in","r",stdin);

     freopen("phi.out","w",stdout);

     prepare();

     scanf("%lld",&n);

     cout<<phi(n);

     return ;

 }

相关文章