Pre TS10 2023 #02 - Ưóc chung lớn nhất khác một (bản khó)

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

Thời gian: 1.0s

Bộ nhớ: 256M

Input: GCD.inp

Output: GCD.out

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 $k$ . Tính số thao tác ít nhất cần phải thực hiện để $a, b > 0$ và $gcd(a, b) \neq 1$ .

Input, Output và Subtasks

Input: (GCD.inp)

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

Output: (GCD.out)

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

Subtasks

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

Sample 1

Input (GCD.inp)

5 9 1

Output (GCD.out)

Note

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

Sample 2

Input (GCD.inp)

2 3 6

Output (GCD.out)

Note

Cộng $18$ cho $2$ và cộng $12$ cho $3$ để có $gcd(20, 15) = 5$ , mất $5$ thao tác.

Bình luận

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