#include <cstdio> //140MS 7772K #include <cstring> #include <cmath> using namespace std; const int N=5000006; //允许的最大数组为2500*2500 const int MAX=10000007; bool temp[N]; int prim[700000]; // 10^7内的素数不超过700000 int isprime(){ //可以返回小于MAX的素数个数 int t=0; prim[t++]=2; int kill=int(sqrt(1.0*MAX))+1; //换时间 for(int i=3;i<kill;i+=2){ if(!temp[i>>1]){ for(int j=i*i;j<MAX;j+=i<<1){ temp[j>>1]=1; } } } kill=MAX>>1; for(int i=1;i!=kill;++i){ if(!temp[i]){ prim[t++]=i<<1|1; } } return t; } __int64 mypow(int n,__int64 m){ __int64 x=2,r=1; while(n){ if(n&1) r=r*x%m; n>>=1; x=x*x%m; } return r; } int main() { //printf("%d\n",isprime()); isprime(); int T,n; __int64 m; scanf("%d",&T); while(T--){ scanf("%d%I64d",&n,&m); int s=0,r=0; while(prim[s]<=n&&prim[s]!=0){ r+=n/prim[s++]; //不会超int } printf("%I64d\n",mypow(r,m)); } return 0; }
In the equation X^2≡X(mod N) where x∈[0,N-1], we define He[N] as the number of solutions.
And furthermore, define HeHe[N]=He[1]*……*He[N]
Now here is the problem, write a program, output HeHe[N] modulo M for a given pair N, M.
显然He[N]表示满足N|x*(x-1)且x<N的非负解的个数。不妨设N=p1^a1*p2^a2*...*pr^ar.因为N|x*(x-1)等价于K*N=x(x-1),又x与(x-1)互素,x=k1*a ,x-1=k2*b 其中a*b=N,k1*k2=K,k1*a-k2*b=1有解当且仅当a,b互素、而且得到的解k1,k2是唯一的。只要a不一样,那么对于的x就不一样。而a有2^r中选择,所以He[N]=2^r.所以对于每个n关键在于求r.又HeHe[N]=He[1]*……*He[N]。所以要求hehe[N]只需求不大于N内的所有正整数有多少个素因子即可。
-------------上述代码拿到了当前最佳解答 ------ 0.肆玖