02/10/2018, 14:33
P144PROC spoj PTIT – ROUND 4C – Lũy thừa
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P144PROC/ 1. Đề bài P144PROC spoj Lũy thừa bậc n của a bằng tích của n thừa số bằng nhau, mỗi thừa số có giá trị bằng a. Cho trước 2 số nguyên a và b, các bạn hãy viết chương trình tính giá trị lũy thừa a^b. Input Gồm nhiều ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P144PROC/
1. Đề bài P144PROC spoj
Lũy thừa bậc n của a bằng tích của n thừa số bằng nhau, mỗi thừa số có giá trị bằng a.
Cho trước 2 số nguyên a và b, các bạn hãy viết chương trình tính giá trị lũy thừa a^b.
Input
Gồm nhiều test, mỗi test ghi trên 1 dòng, gồm 2 số nguyên không âm a và b ( a <= 10^9 và b <= 10^18).
Input kết thúc bởi 2 số 0.
Output
Với mỗi test, ghi ra trên một dòng kết quả phép tính lũy thừa a^b được lấy dư theo 1000 000 007.
Example
Input:
2 3
2 4
3 2
0 0
Output:
8
16
9
2. Gợi ý P144PROC spoj PTIT
– Đây là bài đệ quy cơ bản
TH1: nếu b chia hết cho 2 thì a^b = sqrt(a^(b div 2))
TH2: b không chia hết cho 2 thì a^b = a*(a^(b-1))
Đây là 1 dạng trong phương pháp chia để trị
3. Code tham khảo P144PROC spoj PTIT
const fi=';
du=1000000007;
type data=longint;
var
f:text;
a:int64;
b:int64;
function powermod(a:int64; b:int64):int64;
var t:int64;
begin
if b=0 then exit(1);
if b mod 2 = 0 then
begin
t:=powermod(a, b div 2);
exit((t*t) mod du);
end;
exit( (powermod(a,b-1)*a) mod du );
end;
begin
assign(f,fi); reset(f);
repeat
readln(f,a,b);
if (a=0) and (b=0) then
begin
close(f);
readln;
halt;
end;
writeln(powermod(a,b));
until false;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | const fi='; du=1000000007; type data=longint; var f:text; a:int64; b:int64; function powermod(a:int64; b:int64):int64; var t:int64; begin if b=0 then exit(1); if b mod 2 = 0 then begin t:=powermod(a, b div 2); exit((t*t) mod du); end; exit( (powermod(a,b-1)*a) mod du ); end; begin assign(f,fi); reset(f); repeat readln(f,a,b); if (a=0) and (b=0) then begin close(f); readln; halt; end; writeln(powermod(a,b)); until false; end. |
