欧拉定理(数论定理)在 模幂运算中的应用 | 您所在的位置:网站首页 › 整数指数幂的公式 › 欧拉定理(数论定理)在 模幂运算中的应用 |
< 前言 >
在很多情况下,我们经常会遇到很大的数a和b,求a的b 次幂中的某位数是什么,对于运算,用暴力求解往往会溢出,并且非常麻烦。 而 利用模运算性质和 欧拉定理中的数论定理,则可方便求解超高次幂相关问题。
欧拉定理(数论定理) 内容 在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则: 注: mod为模运算符,在某些地方可表为% φ(n)为1~n中与n互质的数个数) 具体证明见 https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/891345?fr=aladdin#2_2 欧拉的递推式为:
具体用法 例如,我们想知道3333^5555的末位是什么。很明显不可能直接把3333^5555的结果计算出来,那样太大了。但我们想要确定的是3333^5555(%10),所以问题就简化了。 根据 模运算规则 a^b % p = ((a % p)^b) % p ,我们知道3333^5555(%10)= 3^5555(%10)。 根据 模运算规则 (a * b) % p = (a % p * b % p) % p ,由于5555 = 4 * 1388 + 3,我们得到 3^5555(%10) =(3^(4*1388) * 3^3)(%10) =((3^(4*1388)(%10)* 3^3(%10))(%10) =((3^(4*1388)(%10)* 7)(%10)。
化到此处即可使用 欧拉定理 对于3^(4*1388)而言, 3^(4*1388) = (3^4)^1388 (3^4)中Φ(n) = 4,即 n = 10(1,3,7,9满足); 同时 满足 3和10互质, 所以 3^(4*1388)=(1%10)^1388 = 1;
即 根据欧拉定理可以得到 3 ^ (4 * 1388) % 10 = 1, 所以((3^(4*1388)(%10)* 7)(%10)= (1 * 7) (% 10) = 7 计算完毕。 编程实现: //欧拉函数 //求 1..n-1 中与 n 互质的数的个数 int eular(int n){ int ret=1,i; for (i=2;i*i1) ret*=n-1; return ret; } 例题:Super A^B mod C |
CopyRight 2018-2019 实验室设备网 版权所有 |