Định nghĩa: gcd(m, n) là ước số chung lớn nhất của m và n.
Cho số nguyên dương N (3 <= N <= 10^12).
Tìm số nguyên dương M (1 <= M <= N-2) để tổng gcd(M, N) + M đạt giá trị lớn nhất. Nếu có nhiều số M thỏa mãn thì đưa ra số M lớn nhất.
Dữ liệu vào: một số nguyên dương N (3 <= N <= 10^12).
Kết quả: In ra số nguyên dương M tìm được.
Input:
15
Output:
12
Hương được giao nhiệm vụ đo tốc độ bơm của hai máy bơm nước. Để làm như vậy, cô ấy đã sử dụng máy bơm để bơm nước vào bể chứa nước và kiểm tra lượng nước đã được bơm vào bể trong một thời gian cụ thể. Hương phát hiện ra rằng máy bơm thứ nhất bơm được 𝑎 lít nước trong 𝑏 giây và máy bơm thứ hai bơm được 𝑐 lít nước nước trong 𝑑 giây. Nếu khi cả hai máy bơm được sử dụng cùng một lúc, chúng cùng nhau bơm được 𝑏 lít nước trong 𝑑 giây. Thật không may, Hương đã làm đổ nước vào cuốn sổ ghi các giá trị trên và không thể khôi phục các giá trị 𝑎 và 𝑐. Tuy nhiên, cô ấy nhớ rằng những giá trị này là số nguyên dương.
Hãy lập trình giúp Hương xem có bao nhiêu cách để chọn các giá trị 𝑎 và 𝑐 đã bị mất đi.
Dữ liệu vào: một dòng chứa hai số nguyên dương 𝑏, 𝑑 thỏa 1 ≤ 𝑏, 𝑑 ≤10^9.
Kết quả: in ra số cách cần tìm.
Input:
9 6
Output:
4
Input:
40 60
Output:
13
Input:
60 40
Output:
29
Cho một số nguyên dương N.
Yêu cầu: Tách số N thành tổng các số nguyên dương chỉ chứa chữ số 0 và 1. Số lượng số tách được phải là tối thiểu.
Dữ liệu vào: số nguyên dương N (1 <= N <= 10^16).
Kết quả: in ra trên 2 dòng.
Input:
32
Output:
3
10 11 11