a^b ，Pascal编程

显示全部楼层 · 2010-6-24 16:12:36

求a^b
由于结果可能很大，我们现在只需要知道这个值
mod 1012就可以了（为什么是1012？我的生日）
有N组数
n<=5
a<=100
b<=maxlongint;
输入格式：
第1行1个数 n
第2到n+1行两个数a,b
输出格式：
n行每个a^b mod 1012的值

千问 · 2010-6-24 16:12:36

这题和之前那到题目的区别在于这题b的值比较大,所以这题不能采用模拟的方式,因此这题我们采用快速幂下面是程序代码 var i,t,n,a,b:longint; procedure work(b:longint); begin if b=1 then exit; work(b div 2); t:=(t*t)mod 1012; if b mod 2=1 then t:=(t*a)mod 1012; end; begin readln(n); for i:=1 to n do begin readln(a,b); t:=a; work(b); writeln(t); end;

千问 · 2010-6-24 16:12:36

没有那么麻烦吧……varn,a,b,i,j,k:longint;beginreadln(n);for i:=1 to n dobegin
readln(a,b);
k:=1;
for j:=1 to b do
begin
k:=k*(a mod 1012); //余

千问 · 2010-6-24 16:12:36

关于1012 我觉得是你想多了。。a^b 可以这么看：令 c = a^(b div 2)1. b为奇数那么 a^b = c^2 * a2. b为偶数那么 a^b = c^2所以算 a^b 演变成了算 c ，c 的指数为b的一半所以复杂度是log级别的 ~