蒙哥马利算法简介
蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。——百度百科
题目来源——xdoj1372
用到的公式 (a * b) % p = a % p * b % p % p 推论 base^exp % p = （base % p） * （base % p） * … *（base % p） % p（总共exp个小括号） 若为exp偶数 = （base^2 % p) * (base^2 % p) * … * (base^2 % p) % p （总共exp/2个小括号）若exp奇数 = （base^2 % p) * (base^2 % p) * … * (base^2 % p) * base % p % p（总共（exp-1）/ 2个小括号） ……然后一直指数减半，底数平方取模。最后得出答案。 c语言实现 #include<stdio.h>long long int base;//底数long long int exp_1;//指数long long int mod;//取模数long long Montgomery(){ long long int res = 1; while(exp_1) { if (exp_1&1)//如果为奇数 res = (res*base) % mod; exp_1 >>= 1;//指数对半 base = (base*base) % mod;//底数平方 } return res;}int main(){ scanf("%I64d%I64d%I64d", &base, &exp_1, &mod); printf("%I64d", Montgomery()); return 0;} 样例输入 2 10000 10007 样例输出 3909 结语
蒙哥马利算法极大地减少了运算量，并且使得数据规模极大减小。使原本看似不可能完成的程序变得可行。