TLE-oj Cup Round 2 - GCD lũy thừa
Xem PDF
Nộp bài
Điểm:
900 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
128M
Input:
GCDPOW.inp
Output:
GCDPOW.out
Tác giả:
Dạng bài
Cho ba số nguyên dương a, b, n, hãy tính gcd(a^n, b) (a^n là tích của n số a).
Input, Output và Subtasks
Input: (GCDPOW.inp)
- Dòng đầu tiên gồm số nguyên dương T \le 10^5 là số testcases.
- T dòng tiếp theo, mỗi dòng gồm ba số nguyên dương a, b, n.
Output: (GCDPOW.out)
- Gồm T dòng, dòng thứ i là kết quả bài toán thứ i.
Subtasks
- Subtask 1 (15\%): a, n \le 15, b \le 10^{18}.
- Subtask 2 (15\%): a, n \le 10^5, b \le 10^{9}, T \le 10.
- Subtask 3 (20\%): a, n \le 10^9, b \le 10^{9}.
- Subtask 4 (20\%): a, n \le 10^6, b \le 10^{18}, T = 1.
- Subtask 5 (30\%): a, n \le 10^{18}, b \le 10^{18}.
Sample
Input (GCDPOW.inp)
2
6 24 2
2 12 5
Output (GCDPOW.OUT)
12
4
Notes
- Với bài toán thứ nhất, ta có 6^2=36 và gcd(24, 36) = 12.
- Với bài toán thứ hai, ta có 2^5=32 và gcd(12, 32) = 4.
Bình luận