Hướng dẫn giải

~N~ xúc xích bằng nhau được chia thành ~M~ phần ăn bằng nhau. Tìm số lần cắt ít nhất.

Sub 1: Xét từng điểm cắt — ~O(M)~, dùng khi ~M \le 10~

Mỗi phần ăn có độ dài ~N/M~ xúc xích, các điểm cắt nằm tại ~k \cdot N/M~ với ~k = 1, \dots, M-1~. Nếu điểm này là số nguyên thì nó trùng với mối nối giữa hai xúc xích và không cần cắt; ngược lại phải cắt đúng một lần. Đếm số điểm không nguyên.

Nếu chỉ nộp sub này: đúng 7/7 test.

Sub 2: Công thức ước chung lớn nhất — ~O(\log N)~, dùng khi mọi trường hợp còn lại

Trong ~M-1~ điểm cắt có đúng ~\gcd(N, M) - 1~ điểm là số nguyên. Đáp án là ~(M-1) - (\gcd(N, M) - 1) = M - \gcd(N, M)~.

Nếu chỉ nộp sub này: đúng 7/7 test.

Chương trình hoàn chỉnh

Chương trình đọc ~N, M~. Nếu ~M \le 10~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~N=2, M=6~ cho 4 lần cắt; ~N=3, M=4~ cho 3; ~N=6, M=2~ cho 0.

#include <bits/stdc++.h>
using namespace std;

int N, M;   // N xuc xich (do dai 1 moi cai), chia thanh M phan an bang nhau

// Sub 1: vet can. Diem cat thu k la vi tri k*N/M tren day dai N.
// Neu k*N chia het cho M thi diem nay trung moc giua hai xuc xich, khong can cat.
// Nguoc lai phai cat them 1 nhat. Duyet k = 1..M-1. O(M).
void sub1() {
    int cnt = 0;
    for (int k = 1; k < M; k++)
        if ((k * N) % M != 0) cnt++;
    cout << cnt << "\n";
}

// Sub 2: cong thuc. Trong M-1 diem cat, co gcd(N, M) - 1 diem trung moc,
// nen so lan cat = (M - 1) - (gcd - 1) = M - gcd(N, M). O(log).
void sub2() {
    cout << M - __gcd(N, M) << "\n";
}

int main() {
    cin >> N >> M;
    if (M <= 10) sub1();
    else sub2();
    return 0;
}