{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 jie1234567 的文章《循环节 （模取幂运算）》','https://www.xiaopingtou.net/article-53789.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
计算a^(n!) mod c(原创转载请注明)
http://hi.baidu.com/aekdycoin/blog/item/c59bf41112997909213f2ed8.html
什么是循环节？
那么满足条件的最小的b称为循环节开始位置
满足条件的最小的正整数为T称为循环节长度(T>0)
首先通过下面的程序可以很容易的验证
1..106的数，他的循环节不超过106
#include
using namespace std;
const int C=107;
int hash[1000001];
int main()
{
int n,sp,len,i,tmp;
for(n=1;n<=106;n++)
{
memset(hash,0,sizeof(hash));
hash[n%C]=1;
tmp=n;
for(i=2;;i++)
{
tmp*=n;
tmp%=C;
if(hash[tmp%C])break;
}
cout<
return 0;
}
并且循环节的开始位置都是1。
当然这个只是对于比较特殊的数如107才满足开始位置为1，如果对于任意的数，那么循环节的开始位置不一定是1。
下面讨论一般情况
假设a^b mod c的循环节是len,开始位置是spos
定义一个操作op()取得k
0.op(b)
1.if b
最后计算a^k mod c既可
这样可以极大的简化问题,使得b的规模大幅度减小
下面介绍下如何求a^(n!) mod c
有了上面的方法，我相信你们都想到了吧，就是求a^op(n!) mod c
下面开始讨论
op(n!)
if n!
问题又转化为求n!%len
那么
1.n>=len n!%len=0
2.n
当然了过程中不要忘记取mod
当C比较大的时候怎么求循环节？下面给出一个方法
1.令W=C//想想为什么？
2.解模方程
求得最大的b,b为开始位置,w-b为循环节长度
可是当w-b非常大，n却
表示没看懂~~~~~~~ a^bmod n 。logn算法 int modexp（int a,int b,int n） { int t=a,ret=1; whilie(b!=0）{ if（b%2 == 1) ret*=t%n; b/=2; } return ret; }
那么满足条件的最小的b称为循环节开始位置
满足条件的最小的正整数为T称为循环节长度(T>0)
首先通过下面的程序可以很容易的验证
1..106的数，他的循环节不超过106
#include
using namespace std;
const int C=107;
int hash[1000001];
int main()
{
int n,sp,len,i,tmp;
for(n=1;n<=106;n++)
{
memset(hash,0,sizeof(hash));
hash[n%C]=1;
tmp=n;
for(i=2;;i++)
{
tmp*=n;
tmp%=C;
if(hash[tmp%C])break;
}
cout<
return 0;
}
并且循环节的开始位置都是1。
当然这个只是对于比较特殊的数如107才满足开始位置为1，如果对于任意的数，那么循环节的开始位置不一定是1。
下面讨论一般情况
假设a^b mod c的循环节是len,开始位置是spos
定义一个操作op()取得k
0.op(b)
1.if b
最后计算a^k mod c既可
这样可以极大的简化问题,使得b的规模大幅度减小
下面介绍下如何求a^(n!) mod c
有了上面的方法，我相信你们都想到了吧，就是求a^op(n!) mod c
下面开始讨论
op(n!)
if n!
问题又转化为求n!%len
那么
1.n>=len n!%len=0
2.n
当然了过程中不要忘记取mod
当C比较大的时候怎么求循环节？下面给出一个方法
1.令W=C//想想为什么？
2.解模方程
求得最大的b,b为开始位置,w-b为循环节长度
可是当w-b非常大，n却
表示没看懂~~~~~~~ a^bmod n 。logn算法 int modexp（int a,int b,int n） { int t=a,ret=1; whilie(b!=0）{ if（b%2 == 1) ret*=t%n; b/=2; } return ret; }