现在的位置: 首页 > 综合 > 正文

ZOJ2674(指数循环节找不动点) ZOJ2674(指数循环节找不动点)

2017年11月04日 ⁄ 综合 ⁄ 共 2732字 ⁄ 字号 小 中 大 ⁄ 评论关闭

ZOJ2674(指数循环节找不动点)

分类： 数论2013-05-07
16:27 61人阅读 评论(0) 收藏 举报

题目：Strange Limit

 

[cpp] view
plaincopy

  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4. typedef unsigned long long LL;  
  5.   
  6. LL phi(LL n)  
  7. {  
  8.     LL i,m=n;  
  9.     for(i=2;i*i<=n;i++)  
  10.     {  
  11.         if(n%i==0)  
  12.         {  
  13.             m=m-m/i;  
  14.             while(n%i==0) n/=i;  
  15.         }  
  16.     }  
  17.     if(n>1)  
  18.        m=m-m/n;  
  19.     return m;  
  20. }  
  21.   
  22. LL quick_mod(LL a,LL b,LL MOD)  
  23. {  
  24.     LL ans=1;  
  25.     a%=MOD;  
  26.     while(b)  
  27.     {  
  28.         if(b&1)  
  29.         {  
  30.             ans=ans*a%MOD;  
  31.             b--;  
  32.         }  
  33.         b>>=1;  
  34.         a=a*a%MOD;  
  35.     }  
  36.     return ans;  
  37. }  
  38.   
  39. LL f(LL p,LL n,LL MOD)  
  40. {  
  41.     if(n==0) return p%MOD;  
  42.     if(MOD==1||p%MOD==0) return 0;  
  43.     LL pm=phi(MOD);  
  44.     return quick_mod(p,pm+f(p,n-1,pm),MOD);  
  45. }  
  46.   
  47. void Solve(LL p,LL m)  
  48. {  
  49.     LL k=m;  
  50.     while(k-->1) m*=k;  
  51.     LL last = f(p,1,m);  
  52.     LL i = 2;  
  53.     while(1)  
  54.     {  
  55.         LL now = f(p,i,m);  
  56.         if(now == last) break;  
  57.         i++;last=now;  
  58.     }  
  59.     cout<<last<<endl;  
  60. }  
  61.   
  62. int main()  
  63. {  
  64.     LL p,m;  
  65.     bool first=true;  
  66.     while(cin>>p>>m)  
  67.     {  
  68.         if(first) first=false;  
  69.         else      cout<<endl;  
  70.         Solve(p,m);  
  71.     }  
  72.     return 0;  
  73. }  


 由于数据很小，完全可以打表。

[cpp] view
plaincopy

  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4. typedef unsigned long long LL;  
  5.   
  6. LL arr[255][255];  
  7.   
  8. int main()  
  9. {  
  10.     arr[2][2]=0;  
  11.     arr[2][3]=4;  
  12.     arr[2][4]=16;  
  13.     arr[2][5]=16;  
  14.     arr[2][6]=16;  
  15.     arr[2][7]=16;  
  16.     arr[2][8]=25216;  
  17.     arr[2][9]=186496;  
  18.     arr[2][10]=1275136;  
  19.     arr[2][11]=26676736;  
  20.     arr[2][12]=106510336;  
  21.     arr[3][2]=1;  
  22.     arr[3][3]=3;  
  23.     arr[3][4]=3;  
  24.     arr[3][5]=27;  
  25.     arr[3][6]=27;  
  26.     arr[3][7]=27;  
  27.     arr[3][8]=30267;  
  28.     arr[3][9]=151227;  
  29.     arr[3][10]=2691387;  
  30.     arr[3][11]=31721787;  
  31.     arr[3][12]=430889787;  
  32.     arr[5][2]=1;  
  33.     arr[5][3]=5;  
  34.     arr[5][4]=5;  
  35.     arr[5][5]=5;  
  36.     arr[5][6]=245;  
  37.     arr[5][7]=3125;  
  38.     arr[5][8]=23285;  
  39.     arr[5][9]=345845;  
  40.     arr[5][10]=708725;  
  41.     arr[5][11]=18852725;  
  42.     arr[5][12]=18852725;  
  43.     arr[7][2]=1;  
  44.     arr[7][3]=1;  
  45.     arr[7][4]=7;  
  46.     arr[7][5]=103;  
  47.     arr[7][6]=583;  
  48.     arr[7][7]=2023;  
  49.     arr[7][8]=17143;  
  50.     arr[7][9]=339703;  
  51.     arr[7][10]=1428343;  
  52.     arr[7][11]=8685943;  
  53.     arr[7][12]=208269943;  
  54.     arr[11][2]=1;  
  55.     arr[11][3]=5;  
  56.     arr[11][4]=11;  
  57.     arr[11][5]=11;  
  58.     arr[11][6]=131;  
  59.     arr[11][7]=2291;  
  60.     arr[11][8]=2291;  
  61.     arr[11][9]=244211;  
  62.     arr[11][10]=244211;  
  63.     arr[11][11]=244211;  
  64.     arr[11][12]=119994611;  
  65.     LL p,m;  
  66.     bool first=true;  
  67.     while(cin>>p>>m)  
  68.     {  
  69.         if(first) first=false;  
  70.         else      cout<<endl;  
  71.         cout<<arr[p][m]<<endl;  
  72.     }  
  73.     return 0;  
  74. } 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞