| ||||||||||
| 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