题目：所有的平方差
题意：n = a1*a1 - b1*b1,n = a2*a2 - b2*b2,...,n = am*am - bm*bm
其中对于任意的1<=k1,k2<=m，ak1 != ak2 或者 bk1 != bk2，并且ak1,ak2,bk1,bk2>=0
那么我们需要求的是n^(a1*a1+b1*b1+a2*a2+b2*b2+...+am*am+bm*bm)%大质数10000000019的值。
本题注意一点，由于10000000019很大，就是最后求出来的ak与ak在相乘的时候注意一下，比如ak大于10^10时，直接相乘
就会爆LL，我们这里有技巧，就是把乘法变为加法，二分加法，也就是下面的multi函数。
通过本题学到了一招，就是对于求x*x%MOD怎么处理，x与MOD大于10^10。
- #include?<stdio.h>??
- #include?<stdlib.h>??
- #include?<string.h>??
- #include?<algorithm>??
- #include?<iostream>??
- #include?<math.h>??
- ??
- using?namespace?std;??
- typedef?unsigned?long?long?LL;??
- ??
- const?LL?Times=10;??
- const?LL?N=555;??
- const?LL?MOD=10000000018;??
- LL?ct,cnt,c,n;??
- LL?fac[N],num[N];??
- LL?arr[N];??
- LL?gcd(LL?a,LL?b)??
- {??
- ????return?b??gcd(b,a%b):a;??
- }??
- LL?multi(LL?a,LL?b,LL?m)??
- {??
- ????LL?ans=0;??
- while(b)??
- ????{??
- ????????if(b&1)??
- ????????{??
- ????????????ans=(ans+a)%m;??
- ????????????b--;??
- ????????}??
- ????????b>>=1;??
- ????????a=(a+a)%m;??
- ????}??
- return?ans;??
- LL?quick_mod(LL?a,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????LL?ans=1;??
- ????a%=m;??
- ????while(b)??
- ????{??
- ????????if(b&1)??
- ????????{??
- ????????????ans=multi(ans,a,m);??
- ????????????b--;??
- ????????}??
- ????????b>>=1;??
- ????????a=multi(a,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????}??
- return?ans;??
- }??
- bool?Miller_Rabin(LL?n)??
- if(n==2)?return?true;??
- if(n<2||!(n&1))?false;??
- ????LL?a,m=n-1,x,y;??
- ????int?k=0;??
- while((m&1)==0)??
- ????????k++;??
- ????????m>>=1;??
- for(LL?i=0;?i<Times;?i++)??
- ????????a=rand()%(n-1)+1;??
- ????????x=quick_mod(a,m,n);??
- for(LL?j=0;?j<k;?j++)??
- ????????????y=multi(x,n);??
- ????????????if(y==1&&x!=1&&x!=n-1)?false;??
- ????????????x=y;??
- if(y!=1)?true;??
- LL?Pollard_rho(LL?n,LL?c)??
- ????LL?x,y,d,i=1,k=2;??
- ????y=x=rand()%(n-1)+1;??
- while(true)??
- ????????i++;??
- ????????x=(multi(x,n)+c)%n;??
- ????????d=gcd((y-x+n)%n,153); background-color:inherit; font-weight:bold">if(1<d&&d<n)?return?d;??
- if(y==x)?return?n;??
- if(i==k)??
- ????????????y=x;??
- ????????????k<<=1;??
- void?find(LL?n,LL?c)??
- if(n==1)?return;??
- if(Miller_Rabin(n))??
- ????????fac[ct++]=n;??
- return?;??
- ????LL?p=n;??
- ????LL?k=c;??
- while(p>=n)?p=Pollard_rho(p,c--);??
- ????find(p,k);??
- ????find(n/p,k);??
- void?dfs(LL?dept,LL?product=1)??
- if(dept==cnt)??
- if(product<=(LL)sqrt(1.0*n)&&(product+n/product)%2==0&&(n/product-product)%2==0)??
- ????????????arr[c++]=product;??
- return;??
- for(LL?i=0;?i<=num[dept];?i++)??
- ????????dfs(dept+1,product);??
- ????????product*=fac[dept];??
- int?main()??
- ????LL?t,tt=1;??
- ????LL?ans,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????cin>>t;??
- while(t--)??
- ????????cin>>n;??
- ????????printf("Case?%d:?",tt++);??
- if(n==1)??
- ????????????puts("1");??
- continue;??
- ????????ct=0;??
- ????????c=0;??
- ????????find(n,120);??
- ????????sort(fac,fac+ct);??
- ????????num[0]=1;??
- ????????LL?k=1;??
- for(LL?i=1;?i<ct;?i++)??
- if(fac[i]==fac[i-1])??
- ????????????????++num[k-1];??
- else??
- ????????????{??
- ????????????????num[k]=1;??
- ????????????????fac[k++]=fac[i];??
- ????????????}??
- ????????cnt=k;??
- ????????dfs(0,1);??
- ????????sort(arr,arr+c);??
- ????????ans=0;??
- for(LL?i=0;?i<c;?i++)??
- ????????????x=(n/arr[i]+arr[i])/2;??
- ????????????y=(n/arr[i]-arr[i])/2;??
- ????????????ans+=multi(x,MOD)+multi(y,MOD);??
- ????????????ans%=MOD;??
- if(c>0)?cout<<quick_mod(n,ans,MOD+1)<<endl;??
- else????puts("-1");??
- return?0;??
- } ?
