Tìm số nhỏ nhất có thể đạt được trong trò chơi trừ số không phải ước bằng C++

Mô tả bài toán

Cho số n. Mỗi lượt chọn x > 0, x < n, x không chia hết n, trừ x khỏi n. Lặp lại. Tìm giá trị nhỏ nhất có thể của n cuối cùng.

Ví dụ

n=8: chọn 3 → 5, chọn 4 → 1. Output: 1.

Thuật toán

Nếu n=2 thì không thể chọn x (chỉ x=1 nhưng 1 chia hết 2) → kết quả 2. Với n>2, luôn có thể giảm xuống 1.

Code C++

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

int solve(int n) {
    if (n == 2) return 2;
    return 1;
}

int main() {
    int n = 8;
    cout << solve(n) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 8

Output: 1