Description
已知N，求phi(N)
Input
正整数N。N<=10^18
Output
输出phi(N)
Sample Input
8
Sample Output
4
HINT
Source
By FancyCoder
Solution
MillerRabin素数测试模板题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include<iostream> #include<cstdio> #include<ctime> #include<cstdlib> #include<algorithm> #define ll long long using namespace std; ll n,tot,a[10000]; ll cheng(ll x,ll y,ll mo)//¿ìËÙ³Ë { ll ans=0; for (;y;y>>=1) { if (y&1==1) ans=(ans+x)%mo; x=(x+x)%mo; } return ans; } ll mi(ll x,ll y,ll mo)//¿ìËÙÃÝ { ll ans=1; for (;y;y>>=1) { if (y&1==1) ans=cheng(ans,x,mo); x=cheng(x,x,mo); } return ans; } ll gcd(ll a,ll b) { if (b==0) return a;else return gcd(b,a%b); } bool witness(ll a,ll n) { ll u=n-1,t=0; while (!(u&1)) t++,u>>=1; ll x0=mi(a,u,n),x1; for (int i=1;i<=t;i++) { x1=cheng(x0,x0,n); if (x1==1&&x0!=1&&x0!=n-1) return true; x0=x1; } if (x1!=1) return true; return false; } bool MillerRabin(ll n) { if (n==2) return true; if (n%2==0||n<2) return false; int s=30; for (int i=1;i<=s;i++) { ll a=rand()%(n-1)+1; if (witness(a,n)) return false; } return true; } ll ABS(ll x) { if (x<0) return -x; return x; } ll PollardRho(ll x,ll y) { ll i=1,k=2; ll x1=rand()%x; ll y1=x1; while (true) { i++; x1=(cheng(x1,x1,x)+y)%x; ll d=gcd(ABS(y1-x1),x); if (d!=1&&d!=x) return d; if (y1==x1) return x; if (i==k) { y1=x1; k+=k; } } } void Find(ll x) { if (MillerRabin(x)) { tot++; a[tot]=x; return; } ll x1=x; while (x1==x) { ll x2=rand()%(x-1)+1; x1=PollardRho(x1,x2); } Find(x1); Find(x/x1); } int main() { scanf("%lld",&n); if (n==1) { printf("1\n"); return 0; } if (MillerRabin(n)) { printf("%lld\n",n-1); return 0; } tot=0; Find(n); sort(a+1,a+tot+1); tot=unique(a+1,a+tot+1)-a-1; ll phi=n; for (int i=1;i<=tot;i++) phi=phi/a[i]*(a[i]-1); printf("%lld\n",phi); return 0; } |
