#include <stdio.h>
int a,p;
__int64 mod2(int k)
{
	int i;
	__int64 m;
	m = a%p;
	for(i=0;i<k;i++)
		m = (m*m)%p;
	return m;
}
int done()
{
	int k,q=p/2;
	__int64 m(1);
	for(k=0;k<32;k++)
		if(((1<<k)&q)>0)
			m = m*mod2(k)%p;
	if(m==1)
		return 1;
	else
		return -1;
}
void main()
{
	int t,tt;
	scanf("%d",&tt);
	for(t=1;t<=tt;t++)
	{
		scanf("%d%d",&a,&p);
		printf("Scenario #%d:\n%d\n\n",t,done());
	}
}

• a<0 (524) mathzqy 2004-09-06 10:08:45
  • Re:a<0 (7) PC0400322032 2004-09-06 15:34:26
• 这个程序什么原理阿 。。 请教 (506) first 2006-03-28 17:04:57
  • Re:这个程序什么原理阿 。。 请教 (2) 782423381 2009-08-10 22:23:02