pascal 快速幂 怎么写？2^k

k是很大的数。

时间是1S。

肯定要用快速幂， 不懂写。

大牛指教。

function g(x:longint):longint;

var now:longint;

begin

if x=0 then exit(1);

now:=g(x shr 1);

g:=now*now;

if x and 1=1 then

g:=g*2;

end;

这是快速幂的模板，如果是高精度的话把g函数弄成数组就好了。

其思想就是二分的思想。比如2^5=2*((2^2)^2)这样一直分解下去。

function modular(a,b,u:longint):longint; //a 的 b次番 mod n

var d,i,j,k:longint;

begin

d:=1;

for i:=trunc(ln(b)/ln(2))+1 downto 1 do //求 b转化成2进制 的位数

begin

d:=d*d mod n;

if b or (1 shl(i-1))=b then //位运算 判断 第i位 是否为1

d:=d*a mod n;

modular:=d;

end;

呃··这一串程序 不知道为什么 b=0的时候 要特判一下··

就酱紫啦 ··具体思想 可以参考 别的参考书~~我觉得似乎都有的说··

1 shl k； 就行了

2的K次幂是要运算1在第K为的二进制值