CSES - Exponentiation | Lũy thừa - LQDOJ: Le Quy Don Online Judge

CSES - Exponentiation | Lũy thừa

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Pypy 3 3.0s

Python 3 3.0s

Tác giả:

Flower_On_Stone , Phuc_QrdA5

Dạng bài

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hãy tính toán các giá trị \(a^b \mod 10^9\) \(+ 7\) một cách hiệu quả.

Lưu ý: Trong bài này, ta giả định rằng \(0^0 = 1\).

Input

Dòng đầu tiên chứa một số nguyên \(n:\) số lượng câu hỏi.
Sau đó là \(n\) dòng, mỗi dòng chứa hai số \(a,b\).

Output

In ra các giá trị \(a^b \mod 10^9\) \(+\) \(7\).

Constraints

\(1 \leq n \leq 2 \cdot 10^5\)
\(0 \leq a, b \leq 10^9\)

Example

Sample input

Sample output

81
256
921450052

Bình luận

TheBloxdPlayer • 9:21 a.m. 8 Tháng 2, 2025 •

hoangkda copy code chatgpt kìa!!

0
Phản hồi Chia sẻ

lehoangvy • 6:25 p.m. 28 Tháng 10, 2024 •

MOD = 10**9

def power_mod(a, b, mod):
if a == 0 and b == 0:
return 1
result = 1
a = a % mod
while b > 0:
if b % 2 == 1:
result = (result * a) % mod
a = (a * a) % mod
b //= 2
return result

n = int(input().strip())
queries = [tuple(map(int, input().strip().split())) for _ in range(n)]

results = []
for a, b in queries:
value = (power_mod(a, b, MOD) + 7) % MOD
results.append(value)

print("\n".join(map(str, results)))
sai cho nao vay

0
Phản hồi Chia sẻ

code tham khảo

#include <bits/stdc++.h>
using namespace std;
const int M=1e9+7;
#define ll long long
ll bp(ll a, ll b);
int main()
    {                    
        ll t,a,b; cin>>t;
        while (t--)
            cin>>a>>b,
            cout<<bp(a,b)<<"\n";
    }
ll bp(ll a, ll b)
    {         
        int ans=1;
        while (b)
            {
                if (b&1) 
                    ans=(ans*a)%M;
                a=(a*a)%M; b/=2;
            }
        return ans;
    }

Phản hồi

1 phản hồi

TK22NguyenPhat • 8:05 a.m. 24 Tháng 5, 2024 •

Nè :
Python
def modular_exponentiation(a, b, mod):
result = 1
a %= mod
while b > 0:
if b % 2 == 1:
result = (result * a) % mod
b //= 2
a = (a * a) % mod
return result
n = int(input())
for _ in range(n):
a, b = map(int, input().split())
print(modular_exponentiation(a, b, 10**9 + 7))

0
Phản hồi Chia sẻ

thuannguyen1972dn • 6:03 p.m. 2 Tháng 5, 2024 •
PYTHON Mãi đỉnh:
MOD = 10**9 + 7

def powmod(a, b):
kq = 1
while b > 0:
if b % 2 == 1:
kq = (kq * a) % MOD
a = (a * a) % MOD
b //= 2
return kq

def main():
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
index = 1
results = []
for _ in range(n):
a = int(data[index])
b = int(data[index + 1])
result = powmod(a, b)
results.append(result)
index += 2

for res in results: print(res)

if name == "main":
main()
0
Phản hồi Chia sẻ

penistone • 2:26 p.m. 25 Tháng 12, 2023 •

Gợi ý: dùng lũy thừa nhị phân + mod
Code C++: https://ideone.com/rNpdsf

0
Phản hồi Chia sẻ

iq2000laday • 2:55 p.m. 12 Tháng 10, 2023 •

Python AC kiểu chi rứa mọi người 🙁

0
Phản hồi Chia sẻ

1 phản hồi

N7hoatt • 8:47 a.m. 30 Tháng 8, 2023 •
Hãy tính toán các giá trị \(a^b \space\) \(mod\) \(\space 10^9 +7\) một cách hiệu quả.

Lưu ý: trong bài này, ta giả định rằng \(0^0 = 1\).

Input

Dòng đầu tiên gồm số nguyên \(n\): số lượng các tính toán.

\(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(a\) và \(b\).

Output

In giá trị của mỗi \(a^b \space\) \(mod\) \(\space 10^9 +7\).

Constraints

\(1 \leq n \leq 2 \times 10^5\).

\(0 \leq a, b \leq 10^9\).

Example

Test

Input

3 3 4 2 8 123 123

Output

81 256 921450052

Note
0
Phản hồi Chia sẻ

huyhau6a2 • 5:40 p.m. 8 Tháng 9, 2022 •

memory 512K chắc là hơi bé đó ad ơi!

-3
Phản hồi Chia sẻ

1 phản hồi