TIOJ 1199 神奇的模術

[分治]

#include<stdio.h>
#include<stdlib.h>
int pow(long long int n,int x,int y)
{
if(n==1)
return x%y;
else if(n==0)
return 1;
if(n%2)
return (pow(n-1,x,y)*x)%y;
else
{
int r=pow(n/2,x,y);
return (r*r)%y;
}
}
int main()
{
long long int n;
int a,y;
while(scanf("%d %I64d %d",&a,&n,&y)==3)
{
if(!a&&!n&&!y)
break;
if((n==0)&&(a==1))
printf("%d\n",y-1);
else if(n==0)
printf("0\n");
else if((n==1))
printf("1\n");
else
{
int cnt=0;
for(int lx=0;lx<y;lx++)
cnt+=(pow(n,lx,y)==a);
printf("%d\n",cnt);
}
}
}