Thiên Mạnh Chí Tôn

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Authors:
Ain't Mạnh chấp 1 ngày, unKluco
Problem type
📘 Mô tả

Trên Thiên Lộ có hai Thần Đăng khổng lồ là M và P, mang linh lực n1 và n2 (không vượt quá 10^22). Mỗi hồi chuông Thừa Thiên ngân, cả hai giá trị cùng giảm 1. Nghi lễ kéo dài cho tới khi hai giá trị sau khi giảm trở nên *không còn tương ly*—tức chia sẻ cùng một ước chung lớn hơn 1.

Nhiệm vụ là tính **số hồi chuông nhỏ nhất** cần gõ; nếu ngay từ đầu hai giá trị đã hòa linh căn, kết quả là 0.

📥 Input
  • Dòng duy nhất chứa hai số nguyên dương n1 và n2 (1 ≤ n1, n2 ≤ 10^22).
📤 Output

In ra một số nguyên duy nhất — số hồi chuông cần gõ. Nếu không thể in -1

🧪 Ví dụ

Input:

8 15

Output:

1
📎 Ghi chú
  • Ban đầu gcd(8, 15) = 1, còn *tương ly*. Sau 1 hồi chuông, linh lực còn 7 và 14, khi đó gcd(7, 14) = 7 > 1 ⇒ nghi lễ kết thúc.

Comments

Please read the guidelines before commenting.


  • 0
    Ain't Mạnh chấp 1 ngày  commented on July 24, 2025, 2:51 p.m.

    Khi a chia hết cho x và b chia hết cho x thì có 1 toán tử nào đó ghép a vs b lại vẫn chia hết cho x... (lý thuyết số)