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 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.