Divisions

Time Limit: 2000ms

Memory Limit: 262144KB

This problem will be judged on 

CodeForcesGym. Original ID: 

64-bit integer IO format: %I64d      Java class name: (Any)

 

解题：大数质因子分解

1 #include 
       
         2 using namespace std; 3 typedef long long LL; 4 const int maxn = 100001; 5 LL mul(LL a,LL b,LL mod) { 6     if(!a) return 0; 7     return ((a&1)*b%mod + (mul(a>>1,b,mod)<<1)%mod)%mod; 8 } 9 LL quickPow(LL a,LL d,LL n) {10     LL ret = 1;11     while(d) {12         if(d&1) ret = mul(ret,a,n);13         d >>= 1;14         a = mul(a,a,n);15     }16     return ret;17 }18 bool check(LL a,LL d,LL n) {19     if(n == a) return true;20     while(~d&1) d >>= 1;21     LL t = quickPow(a,d,n);22     while(d < n-1 && t != 1 && t != n-1) {23         t = mul(t,t,n);24         d <<= 1;25     }26     return (d&1) || t == n-1;27 }28 bool isP(LL n) {29     if(n == 2) return true;30     if(n < 2 || 0 == (n&1)) return false;31     static int p[5] = {
     2,3,7,61,24251};32     for(int i = 0; i < 5; ++i)33         if(!check(p[i],n-1,n)) return false;34     return true;35 }36 LL gcd(LL a,LL b) {37     if(a < 0) return gcd(-a,b);//特别注意，没这个TLE38     return b?gcd(b,a%b):a;39 }40 LL Pollard_rho(LL n,LL c) {41     LL i = 1,k = 2,x = rand()%n,y = x;42     while(true) {43         x = (mul(x,x,n) + c)%n;44         LL d = gcd(y - x,n);45         if(d != 1 && d != n) return d;46         if(y == x) return n;47         if(++i == k) {48             y = x;49             k <<= 1;50         }51     }52 }53 LL Fac[maxn],tot;54 void factorization(LL n) {55     if(isP(n)) {56         Fac[tot++] = n;57         return;58     }59     LL p = n;60     while(p >= n) p = Pollard_rho(p,rand()%(n-1)+1);61     factorization(p);62     factorization(n/p);63 }64 unordered_map
        
         ump;65 int main() {66     LL x;67     srand(time(0));68     while(~scanf("%I64d",&x)){69         tot = 0;70         if(x == 1) {71             puts("1");72             continue;73         }74         if(isP(x)){75             puts("2");76             continue;77         }78         factorization(x);79         ump.clear();80         for(int i = 0; i < tot; ++i)81             ump[Fac[i]]++;82         unsigned long long  ret = 1;83         for(auto &it:ump) ret *= (it.second + 1);84         printf("%I64u\n",ret);85     }86     return 0;87 }88 /*89 99999999999999998990 10000000770000004991 */