摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:數學

作法:(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;  
}