ayit-#41. 因数的个数-数论

　　搞了两天发现是qpow时大数相乘爆精度了，以前没遇到过，因为大数检测时模数达到了1e18,所以qpow可能会爆，应该利用快速幂原理写一个快速加即可。

　　先筛出1e6以内的质数，然后把x里<=1e6的质因子筛完，这时候x里至多有两个大于1e6因子，可以同时miller下把质数统计走，这样剩下的数都是P1*P2的形式，由于我们只需要知道不同种类因子的个数，可以对剩下的数先两两判断是否不相等且gcd>1，这样就可以把这两个数拆分为四个质因子统计。之后再遍历剩下的数，用之前统计的质因子尝试是否可以被整除，可以的话就把x拆分为两个质因子统计。最后剩下的数含有的质因子就是独特的了。要注意可能出现P1*P1的情况，特判。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<map>
  5 #include<unordered_map>
  6 #include<bits/stdc++.h>
  7 using namespace std;
  8 #define LL long long 
  9 const LL maxn=1000005;
 10 const LL mod=1e9+7;
 11 unordered_map<LL,LL>M;
 12 unordered_map<LL,LL>::iterator it;
 13 LL A[555];
 14 vector<LL>prime;
 15 bool is[1000010];
 16 LL gcd(LL a,LL b){
 17     return b==0?a:gcd(b,a%b);
 18 }
 19 LL Mult(LL x,LL y,LL mod){        //避免两个long long相乘溢出
 20     LL ans=0;ans%=mod;
 21     if(!y)return 0;
 22     while(y){
 23         if(y&1){
 24             ans+=x;
 25             if(ans>=mod)ans-=mod;
 26         }
 27         y>>=1;x<<=1;
 28         if(x>=mod)x-=mod;
 29     }
 30     return ans;
 31 }
 32 LL qpow(LL a,LL b,LL c){
 33     if(a==0) return 0;  LL r=1;
 34     for(;b;b>>=1,a=Mult(a,a,c)) if(b&1)r=Mult(r,a,c);
 35     return r;
 36 } 
 37 LL random(LL n){
 38     return (LL)((double)rand()/RAND_MAX*n+0.5);
 39 }
 40 int judge(LL n){
 41     for(int i=0;i<20;++i){
 42         if(qpow(random(n-2)+1,n-1,n)!=1) return 0;
 43     }
 44     return 1;
 45 }
 46 void init(){
 47     is[0]=is[1]=1;
 48     for(LL i=2;i<=maxn;++i){
 49         if(!is[i]){
 50             prime.push_back(i);
 51         }
 52         for(LL j=0;j<prime.size()&&i*prime[j]<=maxn;++j){
 53             is[i*prime[j]]=1;
 54             if(i%prime[j]==0)break;
 55         }
 56     }
 57 }
 58 bool all(LL n){
 59     LL m=sqrt((long double)n);
 60     if(m*m==n||(m+1)*(m+1)==n||(m-1)*(m-1)==n)return 1;
 61     return 0;
 62 }
 63 vector<LL>S;
 64 int main()
 65 { 
 66     init();
 67     LL n,i,j,ans=1;
 68     scanf("%lld",&n);
 69     for(i=1;i<=n;++i)scanf("%lld",A+i);
 70     for(i=1;i<=n;++i){
 71         if(judge(A[i])){
 72             M[A[i]]++;
 73             A[i]=1;
 74             continue;
 75         }
 76         for(j=0;j<prime.size()&&prime[j]*prime[j]<=A[i];++j){
 77             if(A[i]%prime[j]==0){
 78                 do{
 79                     M[prime[j]]++;
 80                     A[i]/=prime[j];
 81                 }while(A[i]%prime[j]==0);
 82                 if(A[i]>1 &&  judge(A[i])){
 83                     M[A[i]]++;
 84                     A[i]=1;
 85                     break;
 86                 }
 87             }
 88         }    
 89     }
 90     for(i=1;i<=n;++i){
 91         if(A[i]==1)continue;
 92         for(j=i+1;j<=n;++j){
 93             if(A[j]==1 || A[i]==A[j]) continue;
 94             LL ret=gcd(A[i],A[j]);
 95             if(ret!=1){
 96                 M[ret]+=2;
 97                 if(A[i]/ret!=1)M[A[i]/ret]++;
 98                 if(A[j]/ret!=1)M[A[j]/ret]++;
 99                 A[i]=A[j]=1;
100             }
101         }
102     }
103     for(i=1;i<=n;++i){
104         if(A[i]!=1){
105             for(it=M.begin();it!=M.end();it++){
106                 if(A[i]%(it->first)==0){
107                     A[i]/=it->first;
108                     it->second++;
109                     M[A[i]]++;
110                     A[i]=1;
111                 } 
112             }
113         }
114     }
115     for(i=1;i<=n;++i){
116         if(A[i]!=1)S.push_back(A[i]);
117         }
118     sort(S.begin(),S.end());
119     S.push_back(1);
120     i=0;
121     LL x=1;
122     while(i<S.size()-1){
123         while(S[i+1]==S[i])i++,x++;
124         if(all(S[i])) (ans*=(x*2+1))%=mod;
125         else (((ans*=(x+1))%=mod)*=(x+1))%=mod;
126         i++,x=1;
127     }
128     for(it=M.begin();it!=M.end();it++)
129          if(it->first!=1)(ans*=(it->second+1))%=mod;
130     printf("%lld
",ans);
131     return 0;
132 }