本题的注意点：n=p1*p2*p3......Pm

解法：直接利用公式a^((p-1)/2)=(a/p)mod p 即可求解。

 

#include
    
     #include
     
      int flag[1005],p[500],a;int d[100];int init(int s){	int len=0,tmp,h=sqrt(s+0.5);    for(int i=0;p[i]<=h;i++)	if(s%p[i]==0)	{		if(a%p[i]==0)return -1;		while(s%p[i]==0)		{		    d[len++]=p[i];			s/=p[i];		}		if(s==1)return len;	}	if(s>1)	{		if(a%s==0)return -1;//这地方该开始忘了判断了，查错查了好久TTT		d[len++]=s;	}	return len;}int getans(int x,int s){	int tmp=s/2;	__int64 ans=1,b=x;	while(tmp>0)	{		if(tmp&1)ans=ans*b%s;		b=b*b%s;		tmp/=2;	}	if(ans!=1)return -1;	return 1;}int main(){	int i,j,k=0,n;	for(i=2;i<1000;i++)	{		if(!flag[i])		{			p[k++]=i;			for(j=i*i;j<1000;j+=i)				flag[j]=1;		}	}	while(scanf("%d%d",&a,&n)!=-1)	{		int len=init(n);		if(len==-1)		{			printf("0\n");			continue;		}		int ans=1;        for(i=0;i