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

ac代码

Posted by 1548669491 at 2012-05-01 23:19:38 on Problem 3641
#include<stdio.h>
#include<math.h>
int main()
{
	__int64 a,p,n,i,j;
	__int64 exp_mod(__int64 a,__int64 b,__int64 n);
	int isPrime(__int64 n);
	while(scanf("%I64d %I64d",&p,&a)!=EOF&&(a+p)!=0){
		if(isPrime(p))
			printf("no\n");
		else{
			if(exp_mod(a,p,p)==a)
				printf("yes\n");
			else
				printf("no\n");
		}
	
	}
	return 0;
	
	
}

int  isPrime(__int64 n)
{
	int i;
    if(n<2)
        return 0;
    if(n==2)
        return 1;
    for(i=3;i*i<=n;i=i+2)
        if(n%i==0)
            return 0;
        if(i*i>n)
            return 1;
}
__int64 exp_mod(__int64 a,__int64 b,__int64 n){
	__int64 r=1;
	while(b){
		if(b&1)
			r=(r*a)%n;
		a=(a*a)%n;
		b>>=1;
	}
	return r;
}

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