快速幂求余算法快速幂求余算法（OJ T1128）求 ab%c（这就是著名的 RSA 公钥的加密方法）当 a,b 很大时，直接求解这个问题不太可能，你能想到哪些优化呢？算法算法 1：直观上，也许最容易想到的是利用a*b%c=(a%c)*b)%c，这样每一步都进行这种处理，这就解决了 ab 可能太大存不下的问题，但这个算法的时间复杂度依然是 O(n)，根本没有得到优化。当 b 很大时运行时间会很长算法算法 2：另一种算法利用了分治的思想，可以达到 O(logn)。 可以把 b 按二进制展开为b=p(n)*2n+p(n-1) *2(n-1)+.+p(1)*2+p(0) 其中 p(i) (0=1) if(k%2=1) b=a*b%m; a=a*a%m; k=k/2; return b; 例题一、高级机密Time Limit:1000MS Memory Limit:65536K Total Submit:43 Accepted:16 DescriptionDescription 在很多情况下，我们需要对信息进行加密。特别是随着 Internet 的飞速发展， 加密技术就显得尤为重要。 很早以前，罗马人为了在战争中传递信息，频繁地使用替换法进行信息加密。 然而在计算机技术高速发展的今天，这种替换法显得不堪一击。因此研究人员 正在试图寻找一种易于编码、但不易于解码的编码规则。 目前比较流行的编码规则称为 RSA，是由美国麻省理工学院的三位教授发明的。 这种编码规则是基于一种求幂取模算法的：对于给出的三个正整数 a，b，c， 计算 a 的 b 次方除以 c 的余数。 你的任务是编写一个程序，计算 abmod c。InputInput 输入数据只有一行，依次为三个正整数 a，b，c，三个正整数之间各以一个空 格隔开，并且 1=1) if(b%2=1) result=a*result%c; a=a*a%c; b/=2; /通过b/2来求得p(i)为1还是0 return result;二、D: Raising Modulo NumbersTime Limit: 1000 ms Case Time Limit: 1000 ms Memory Limit: 30000 KBSubmit: 24 Accepted: 7 DescriptionPeople are different. Some secretly read magazines full of interesting girls pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODKH. The rules follow: Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players experience it is possible to increase the difficulty by choosing higher numbers. You should write a program that calculates the result and is able to find out who won the game.InputThe input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 long long z,h,a,b,m,ans,pow;int main() scanf(“%I64d“,while(z-)scanf(“%I64d %I64d“,ans=0;while(h-)scanf(“%I64d %I64d“,pow=1;while(b=1)if(b%2=1)pow=a*pow%m;a=a*a%m;b/=2;ans+=pow;ans%=m; printf(“%I64dn“,ans);return 0;