Nguồn đề bài: http://www.spoj.com/PTIT/problems/P144PROC/
Nội dung bài viết
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
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. |
Bài viết liên quan
- P151SUMB spoj PTIT – ROUND 1B – Đong gạo
- BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K
- PTIT122F spoj PTIT – Số siêu tự nhiên
- P132SUMJ spoj PTIT – SUM2 J – Hoán vị chữ số
- BCSRETAN spoj PTIT- Số may mắn thứ K
- BCCOW spoj PTIT – Đi xem phim
- P134SUMG PTIT spoj – SUM4 G – Gia vị
- BCPERMU PTIT spoj – Liệt kê hoán vị (Cơ bản)
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
ai có code c k ạ
có bạn ạ. xem tại: http://ideone.com/iqM5PH
#include
#define e 1000000007
using namespace std;
int a;
long long b;
int lt(int a, long long b)
{
if(b==0) return 1;
int t=lt(a,b/2);
t=((long long)t*t)%e;
if(b%2) t=((long long)t*a)%e;
return t;
}
int main()
{
while(1)
{
cin>>a>>b;
if(a==0&&b==0) break;
int kq=lt(a,b);
cout<<kq<<"n";
}
}
có bạn à.
bạn xem tại đây: http://ideone.com/iqM5PH
cảm ơn bạn đã quan tâm tới site
#include
#define e 1000000007
using namespace std;
int a;
long long b;
int lt(int a, long long b)
{
if(b==0) return 1;
int t=lt(a,b/2);
t=((long long)t*t)%e;
if(b%2) t=((long long)t*a)%e;
return t;
}
int main()
{
while(1)
{
cin>>a>>b;
if(a==0&&b==0) break;
int kq=lt(a,b);
cout<<kq<<"n";
}
}