ACM 374 Q374: Big Mod
作法:數學
作法:(1)由於%的數字很小 , 利用陣列找循環
(2)離散數學(感謝teching提供)
第2個程式碼的↓
在此提供暴力的循環,速度很慢...
注意:1.循環不一定從頭開始
/*********************************************************/
#include <stdio.h>
int f(int m,int n, int mod)
{
long long int mul=m;
long long int r=1;
while(n){
if(n%2==1){r*=mul;r%=mod;}
mul*=mul;
mul%=mod;
n>>=1;
}
return r;
}
int main()
{
int B,P,M;
while(scanf("%d%d%d",&B,&P,&M)==3)
printf("%d\n",f(B,P,M));
return 0;
}
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
main()
{
int B,P,M;
while(scanf("%d %d %d",&B,&P,&M)==3)
{
if(P==0) {printf("1\n");continue;}
int circle[46341]={0},BP[46341]={0};
int circleL[46341]={0};
int n=B%M,L=1,now=B%M;
while(circle[now]!=1&&L<=P)
{
circle[now]=1;
BP[L]=now;
circleL[now]=L;
L++;
now=now*n%M;
}
if(P>=L)
{
L=L-circleL[now];
P=P-circleL[now];
P=P%L;
P=P+circleL[now];
}
printf("%d\n",BP[P]);
}
return 0;
}