原文：http://hi.baidu.com/fenglehuo/blog/item/3ce1f7b4a0ffd67e8bd4b2d8.html
求a^b%c（這就是著名的RSA公鑰的加密方法）
當(dāng)a,b很大時(shí)，直接求解這個(gè)問(wèn)題不太可能
你能想到哪些優(yōu)化呢？
算法1：直觀上，也許最容易想到的是利用a*b%c=((a%c)*b)%c,這樣每一步都進(jìn)行這種處理，這就解決了a^b可能太大存不下的問(wèn)題，但這個(gè)算法的時(shí)間復(fù)雜度依然是O(n)，根本沒(méi)有得到優(yōu)化。當(dāng)b很大時(shí)運(yùn)行時(shí)間會(huì)很長(zhǎng)
算法2：另一種算法利用了分治的思想，可以達(dá)到O(logn)。
可以把b按二進(jìn)制展開(kāi)為b=p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)
其中p(i) (0<=i<=n)為0或1
這樣a^b=a^(p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0))
=a^(p(n)*2^n)*a^(p(n-1)*2^(n-1))*...*a^(p(1)*2)*a^p(0)
對(duì)于p(i)=0的情況,a^p(i)*2^(i-1)=a^0=1,不用處理
我們要考慮的僅僅是p(i)=1的情況
a^(2^i)=(a^(p(i)*2(i-1)))^2
利用這一點(diǎn)，我們可以遞推地算出所有的a^(2^i)
當(dāng)然由算法1的結(jié)論，我們加上取模運(yùn)算a^(2^i)%c=((a^(2(i-1))%c)*a^(2(i-1)))%c
于是再把所有滿足p(i)=1的a^(2^i)%c按照算法1乘起來(lái)再%c就是結(jié)果示例:
3^6%7=3^(2^2)*3^(2^1)%7
=((3^(2^1))^2%7)*(3^1*3^1%7)
=(((3^1*3^1%7)%7)^2%7*2%7)%7
=(4*2)%7
=8%7
=1
當(dāng)然算法可以進(jìn)一步改進(jìn)，比如二進(jìn)制的每一位不必存起來(lái)，可以邊求邊用
經(jīng)改進(jìn)后代碼如下：（輸入a,k,m,求a^k%m)
long f(long a,long k,long m)
{
long b=1;
while(k>=1)
{
if(k%2==1) b=a*b%m;
a=a*a%m;
k=k/2;
}
return b;
}
例題
D: Raising Modulo Numbers
Time Limit: 1000 ms Case Time Limit: 1000 ms Memory Limit: 30000 KB
Submit: 24 Accepted: 7
Description
People 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 KOKODáKH. 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.
Input
The 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 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.
Output
For each assingnement there is the only one line of output. On this line, there is a number, the result of expression
(A1B1+A2B2+ ... +AHBH)mod M.
Sample Input
3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 17 1 3 18132
Sample Output
2
13195
13
題意
給出A1~Ah,B1~Bh,M,H,求(A1B1+A2B2+ ... +AHBH)mod M.
做法
快速冪取模+累加步步取模
HIT
取模相當(dāng)于在原數(shù)中不斷減去M直到原數(shù)小于M，所以累加后取模和步步取模結(jié)果相同，因此在累加過(guò)程中取模以防止超過(guò)long long界限
CODE
#include <stdio.h>
long long z,h,a,b,m,ans,pow;
int main(){
scanf("%I64d",&z);
while(z--){
scanf("%I64d %I64d",&m,&h);
ans=0;
while(h--){
scanf("%I64d %I64d",&a,&b);
pow=1;
while(b>=1){
if(b%2==1)
pow=a*pow%m;
a=a*a%m;
b/=2;
}
ans+=pow;
ans%=m;
}
printf("%I64d\n",ans);
}
return 0;
}