GCD Lũy Thừa

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
TCA_Khoa
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Lũy thừa một phép toán hai ngôi của toán học thực hiện trên hai số a và b, kết quả của phép toán lũy thừa là tích số của phép nhân : có b thừa số a nhân với nhau. Lũy thừa ký hiệu là a^b, đọc là lũy thừa bậc b của a, số a gọi là cơ số, số b gọi là số mũ.

Trong toán học, nếu số nguyên a chia hết cho số nguyên b thì số b được gọi là ước của số nguyên a, a được gọi là bội của b. Số nguyên dương u lớn nhất là ước của cả hai số nguyên a, b được gọi là ước số chung lớn nhất (ƯCLN) của a và b.

Trong bài tập này bạn được giao 3 số nguyên \(A, B\) và \(N\). Bạn cần viết chương trình tìm ước chung lớn nhất của \(A^N\) và \(B\). Hay GCD(\(A^N\), \(B\)).

Input

  • Chứa 3 số nguyên \(A, B, N (1 ≤ A, B, N ≤ 10^9)\)

Output

  • Một dòng duy nhất là GCD thu được.

Example

Test 1

Input 
2 3 3
Output 
1

Test 2

Input 
2 4 5
Output 
4

Bình luận