TS10 Vũng Tàu 2022 - Bài 2
Xem dạng PDF
Gửi bài giải
Điểm:
11,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Ước chung lớn nhất của 2 số nguyên dương ~x~ và ~y~ (kí hiệu: ~\text{UCLN}(x, y)~) là một số nguyên dương ~z~ ~(z > 0)~ lớn nhất sao cho cả ~x~ và ~y~ đều chia hết cho ~z~.
Cho hai số nguyên dương ~a, b~ ~(1 < a < b \le 10^{18})~.
Yêu cầu: Cho biết số nguyên dương ~x~ ~(x \ge 0)~ nhỏ nhất sao cho ~\text{UCLN}(a + x, b + x) = b - a~.
Input
Một dòng duy nhất chứa 2 số nguyên dương ~a~ và ~b~ cách nhau một kí tự trắng.
Output
Ghi ra một số nguyên dương ~x~ ~(x \ge 0)~ duy nhất thỏa mãn yêu cầu của bài toán.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~50\%~ | ~0 < a < b \le 10^6~ |
| 2 | ~50\%~ | ~0 < a < b \le 10^{18}~ |
Sample Input 1
5 9
Sample Output 1
3
Notes
~x = 3~ là số nguyên dương nhỏ nhất tìm được thỏa mãn yêu cầu bài toán. Cụ thể: ~\text{UCLN}(a + 3, b + 3) = \text{UCLN}(5 + 3, 9 + 3) = \text{UCLN}(8, 12) = 4 = b - a = 9 - 5~.
Bình luận