模取幂 c=a^b mod n 求c
【转模取幂】
（我以实例为例，因为说到底还是实例才能说清楚）
a=5;b=22;c=50;(其实a 和 c 取多少都和这里要说的没什么关系，只要看b就可以了) b的二进制表示为10110。
如果从右往左遍历该二进制序列，则第一位是0；若一个数的二进制表示中末尾为0，说明什么？对~~说明该数是能够被2整除的。那么 a^b = a^(A*2) (b=2A)
则a^b mod n =( a^A * a^A ) mod n
根据上面的公式: (a * b) mod c=((a mod c)* b) mod c
得 ( a^A * a^A ) mod n = ((a^A mod n) * a^A) mod n (一步一步写的我好辛苦)
a^A 是啥？对~~ a^A 不就是10110 右移一位嘛，就是1011（右移一位等于原数除以2，这个不用我说了吧）。
那么，就是从右往左遍历到第二位了。第二位是1，说明什么？对~~说明这个数不能被2整除…则 a^A =a^(B+1)....(A=B+1),
即 a^A =a^B * a
那么，a^A mod n =((a^B mod n) * a ) mod n
a^B 是多少？对~~ 其实 B不已经是偶数了嘛。
用之前的方法类推，a^B mod n = ((a^C mod n) * a^C) mod n ......（B=2C）
原式 a^A mod n =((a^B mod n) * a ) mod n = (((a^C mod n) * a^C ) mod n) * a ) mod c （注意区分大小写，A，B，C和原来的a,b,c不是一回事）
a^C 又是啥？以此类推。一直将二进制序列右移，反复嵌套，直到最后一位，就OK啦！
【分析】
好像根本不用那么复杂地去理解，直接快速幂加高精度去AC，过程中一律取模。
高精度就只用对B操作，每次除以2.
我写的程序参照前面转载的资料分析。
（其实真的感觉都是快速幂啊，只不过给取模工作得到些理论依据）
【代码1】【本人的】
type arr=array[0..150]of integer;
var n,a,i:longint;
b:arr;
ss:string;
function di(b:arr):arr;
var p:arr;
i:integer;
begin
fillchar(p,sizeof(p),0);
for i:=b[0] downto 1 do
begin
p[i]:=b[i] div 2;
b[i-1]:=b[i-1]+(b[i] mod 2)*10;
end;
p[0]:=b[0];
while p[p[0]]=0 do dec(p[0]);
di:=p;
end;
function f(b:arr):int64;
var l:int64;
begin
if (b[1]=1)and(b[0]=1)then
begin
f:=a mod n;
exit;
end;
l:=f(di(b));
l:=l*l mod n;
if odd(b[1])then l:=l*(a mod n) mod n;
f:=l;
end;
begin
assign(input,'t3.in');reset(input);
assign(output,'t3.out');rewrite(output);
readln(a);
readln(ss);
b[0]:=length(ss);
for i:=1 to length(ss) do
b[length(ss)-i+1]:=ord(ss[i])-48;
readln(n);
writeln(f(b));
close(input);close(output);
end.
【代码2】【朋友的】【感觉很优美】
type ch=array[0..1000] of integer;
var b:ch;
s:string;
i,j,n,l:longint;
ans,a:int64;
procedure chu(var a:ch);
var i,k:longint;
begin
k:=0;
for i:=a[0] downto 1 do
begin
a[i]:=10*k+a[i];
k:=a[i] mod 2;
a[i]:=a[i] div 2;
end;
while (a[a[0]]=0)and(a[0]>0) do dec(a[0]);
end;
begin
assign(input,'t3.in');reset(input);
assign(output,'t3.out');rewrite(output);
readln(a);
readln(s);
readln(n);
l:=length(s);
b[0]:=l;
for i:=1 to l do
b[l-i+1]:=ord(s[i])-ord('0');
ans:=1;
while b[0]<>0 do
begin
if odd(b[1]) then ans:=(ans*a) mod n;
a:=a*a mod n;
chu(b);
end;
writeln(ans);
close(input);close(output);
end.