【欧拉定理】计算(a^(b^c))%1000000007

时间：2015-06-05 11:57:13 阅读：812 评论：0 收藏：0 [点我收藏+]

欧拉定理（称费马-欧拉定理或欧拉函数定理）

欧拉定理表明，若n,a为正整数，且n,a互素(即gcd(a,n)=1)，则

技术分享

这个定理可以用来简化幂的模运算。比如计算7²²²的个位数，实际是求7²²²被10除的余数。7和10互素，且fai(10)=4。由欧拉定理知

技术分享

所以

技术分享

则对于(a^{b^c})%1000000007

根据欧拉定理, a的fai(1000000007)和1同余，那么把b^c分解成(n*fai(m)+r)的形式，(a^{b^c}) 就变成了 A⁽^n*fai(m)+r)，那么就变成了 A^(n*fai(m)*A^r，又A^(n*fai(m)和1同余，那么只要求A^r即可。

已知fai(m)是同1到与m互质的数的个数，故应为100000006。

原文：http://www.cnblogs.com/LLGemini/p/4554127.html

踩

(0)

评论一句话评论（0）

分享档案

更多>