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

79愛的鼓勵 1訂閱站台

題目意思為質數序列的次方%76543

接下來就利用分而治之加快計算次方的次數

/******************************************************/

#include<stdio.h>  
#include<stdlib.h>  
int Prime[5200]={0},p;  
int prime()  
{  
  char num[50001]={0};  
  int a,b,m=0;  
 for(a=2;a<50000;a++)     
      if(num[a]==0)     
        {     
           Prime[m++]=a;     
           for(b=2;a*b<=50000;b++)     
             num[a*b]=1;     
        }  
   return m;  
}  
long long int f(int m,int n, int mod)
{   
  long long int mul=m;   
  long long int r=1;   
  while(n)
   {   
      if(n&1)  r*=mul,r%=mod;
      mul*=mul,mul%=mod,n/=2;   
   }   
  return r;   
}
main()  
{  
 p=prime(); 
 long long int ANS=1;
 int n,time=0;
 while(scanf("%d",&n)==1)
      ANS*=f(Prime[time++],n,76543),ANS%=76543;
 printf("%lld\n",ANS);
 return 0;     
}