Pre TS10 2023 #01 - Ưóc chung lớn nhất khác một

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python, ~~text~~

Bạn được cho hai số nguyên dương $a, b$ . Với mỗi thao tác, bạn được cộng hoặc trừ một trong hai số cho $1$ . Tính số thao tác ít nhất cần phải thực hiện để $gcd(a, b) \neq 1$ .

Input, Output và Subtasks

Input: (bàn phím)

Một dòng duy nhất gồm hai số nguyên dương $a, b$ $(a, b \le 10^6)$

Output: (màn hình)

Một dòng duy nhất là số thao tác ít nhất cần sử dụng.

Subtasks

Subtask 1 ( $60\%$ ): $a, b \le 1000$ .
Subtask 2 ( $40\%$ ): Không có giới hạn gì thêm.

Sample

Input (bàn phím)

5 9

Output (màn hình)

Note

Cộng $5$ cho $1$ để có $gcd(6, 9) = 3$ , mất $1$ thao tác.

Bình luận

Không có bình luận nào.