Hai số nguyên a và b được gọi là nguyên tố cùng nhau (coprime) nếu gcd(a, b) = 1. Tính chất này quan trọng khi chọn số mũ công khai e trong RSA (cần gcd(e, phi(n)) = 1).
Hãy dùng thuật toán Euclid để tính ước chung lớn nhất rồi kết luận.
Input:
8 15
Output:
YES
gcd(8, 15) = 1 nên 8 và 15 nguyên tố cùng nhau.
Một dòng chứa hai số nguyên a và b cách nhau bởi dấu cách.
0 <= a, b <= 10^18
In YES nếu a và b nguyên tố cùng nhau, ngược lại in NO.
Ví dụ:
Đầu vào:
8 15
Đầu ra:
YES
Giải thích:
Đang tải editor...