Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WHY Wrong?

Posted by wanpi0user at 2005-06-17 23:27:18 on Problem 1845
谁能帮我看看我的程序吗?先谢谢了。
//////////////////////////////////////////////////
//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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator