POWER1 - Tính lũy thừa 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho hai số nguyên dương ~a~ và ~n~. Tính ~a^n~.
Input
- Gồm một dòng duy nhất ghi hai số nguyên dương ~a~ và ~n~ cách nhau bởi dấu cách.
Giới hạn:
- ~1 ≤ a, n ≤ 10^9~.
Output
- Phần dư của phép tính ~a^n~ chia cho ~10^9 + 7~.
Sample
Input #1
5 7
Output #1
78125
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std; const long long mod=1e9+7; ll n,k; ll Mul(ll a,ll b){ if(b==0) return 0ll; ll tmp=Mul(a,b/2); if(b&1) return (tmp2+a)%mod; return tmp2%mod; } ll Pow(ll n,ll k){ if(k==0)return 1; if(k==1)return n%mod; ll tmp=Pow(n,k/2); ll a=Mul(tmp,tmp); if(k&1) return a*n%mod; return a%mod; } int main(){ iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; cout<<Pow(n,k); }
include <bits/stdc++.h>
using namespace std; const long long MOD = 1000000007;
long long modexp(long long a, long long n) { long long res = 1 % MOD; a %= MOD; while (n > 0) { if (n & 1) res = (res * a) % MOD; a = (a * a) % MOD; n >>= 1; } return res; }
int main() { long long a, n; cin >> a >> n; cout << modexp(a, n) << "\n"; return 0; }
include <bits/stdc++.h>
using namespace std; const long long MOD = 1e9 + 7;
long long power(long long a, long long n) { long long res = 1; a %= MOD; // Đảm bảo a không vượt quá MOD while (n > 0) { if (n % 2 == 1) res = (res * a) % MOD; // Nếu bit lẻ a = (a * a) % MOD; // Bình phương cơ số n /= 2; // Dịch phải (chia 2) } return res; }
int main() { long long a, n; cin >> a >> n; cout << power(a, n); }
Nếu bạn sử dụng C++. Sẽ cần kiến thức về luỹ thừa nhị phân và phép nhân Ấn Độ, nếu bạn chưa có kiến thức về 2 kỹ thuật này thì có thể tham khảo thêm (mình để link bài viết ở đây)
https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj
các bạn tham khảo phép tính dư module kết hợp với lũy thừa nhị phân là đc
Var x,y:int64; Function LUTH(a,b:int64):int64; Var k,h:int64; Begin If b = 1 then exit(a mod 1000000007); k:=b div 2; h:=a*a mod 1000000007; If b mod 2 = 0 then exit(LUTH(h,k) mod 1000000007) Else exit((LUTH(h,k) mod 1000000007) * a mod 1000000007); End; Begin Read(x,y); Write(LUTH(x,y)); Readln; End.
Nhờ các bạn AC giùm Test cuối với. Mình bị TLE
dùng lũy thừa nhị phân là AC