首先谢谢ZhangJunHua提供的思路,就是每乘一次取余,乘p次,虽然简单,但是我没想出来: )

在解决了他思路上的时间效率问题后终于AC,也就是提供一个a^1000次方,每次以1000的速度增长,这样终于AC了,但是时间效率很低

看到各位大牛通过的都是0ms,16ms! 故在此求解.

顺便也把我代码贴出来,供跟我一样水平的人参考!

#include <iostream>
#include <cmath>
using namespace std;

int ChkPrime(int x)
{
	int i;
	if (x==2)
		return 1;
	if (x%2==0)
		return 0;
	for (i=3;i<sqrt((float)x);i+=2)
		if (x%i==0)
			return 0;
	return 1;
}

int main()
{
	int p,a,i;
	long long temp=1,a_1000;        
	while(cin>>p>>a)
	{
		if (p==0&&a==0)
			break;
		else
		{
			temp=1;
			if (ChkPrime(p))
			{
				cout<<"no"<<endl;
				continue;
			}
			a_1000=a;
			for (i=1;i<1000;i++)
				a_1000=(a_1000*a)%p;
			for (i=0;i<p-999;i+=1000)
				temp=(temp*a_1000)%p;
			for (;i<p;i++)
				temp=(temp*a)%p;
			if (temp==a)
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}
	}
	return 0;
}

• Re:终于AC了, 但是却和大家有很多差距! (12) talabanr 2008-07-20 09:32:32