Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WHY Wrong?谁能帮我看看我的程序吗?先谢谢了。 ////////////////////////////////////////////////// //wanpi0user ////////////////////////////////////////////////// #include<iostream> #include<string> #include<fstream> #include<cmath> using namespace std; int xmod_1(int a,int b);//求a^-1 mod b; int module(__int64 x,__int64 r,__int64 n);//求x^r mod n int main(){ int fac[10],pfac[10],num,i,t,j,r,x,y,z,base; while(1){ for(i=0;i<10;i++){ fac[i]=0;pfac[i]=0; } cin>>num>>base;j=0;t=num; /*step1 fac the num;*/ if(base==0||num==1){ cout<<1<<endl;return 0;}//指数为0,或基数为1均返回1 if(num==0){ cout<<0<<endl;return 0;}//基数为0返回0 if(num%9901==0) { cout<<0<<endl;return 0;}//如果基数为9901的倍数,直接返回0 while(num%2==0){ fac[j]=2;pfac[j]++;num/=2; } if(t!=num) ++j; r=ceil(sqrt(num)); for(i=3;i<=r;i+=2){ if(num%i==0){ //cout<<i<<"OK!"<<endl; do{ fac[j]=i;pfac[j]++;num/=i; }while(num%i==0); ++j; } r=ceil(sqrt(num)); } if(num>1){ if(fac[j]) j++;fac[j]=num;pfac[j]++;} //i=0;do{cout<<fac[i]<<"*"<<pfac[i]<<" ";}while(fac[++i]); /*step2 x=pi(p[i]-1);x*/ i=0;x=1;do{x*=(fac[i]-1);}while(fac[++i]);//cout<<x<<endl; /*step3 calc x^(-1) % 9901 ->y;*/ y=xmod_1(x,9901); /*step4 calc(pi(p[i]^(e[i]+1)-1) % 9901->z;*/ num=1;i=0; do{ num*=(module(fac[i],pfac[i]*base+1,9901)-1); num=(num+9901)%9901; }while(fac[++i]); z=num*y%9901; /*step5 output z;*/ cout<<z<<endl; break;//只有1case } return 0; } int xmod_1(int a,int b){ int i,aa=a%b; for(i=1;i<b;i++){ if(i*aa%b==1) break; } return i; } int module(__int64 x,__int64 r,__int64 n){ __int64 a,b,c; a=x;b=r;c=1;//1 while(b){ while(b%2==0){b/=2;a=a*a%n;}//4 b--;c=c*a%n;//3,5 } return static_cast<int>(c);//2 } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator