【ABC161】F - Division or Subtraction

atcoder.jp

解法

次のように定義する。
操作1、N が K で割り切れるとき、N を N/K に置き換える
操作2、そうでないとき、N を N−K に置き換える

場合分けして考える。

操作2だけでNを1にできるような数

これは、N-1の1以外の約数すべてが該当する。

理由

m回操作2を行うとNは、になる。(ただし、m≠0)
これが1になるとき、という方程式を立てることができ、変形すると、になる。
mは整数であるため、KはN-1の約数になることがわかった。

操作1を1回以上行って、Nを1にできるような数

これはNの約数のうち、最初に操作1をn回行ったのち、操作2をm回行うことによってNを1にできるような数が該当する。

理由

操作2を1回でも行ったあとに、操作1をすることはできない。
これは、 であり、操作2を何回行ってもKで割り切れる数になることはないから。
そのため、操作1は最初にしか行うことができず、最初に操作1を行うことができる数は、Nの約数が該当する。

実装

Nが2以外の場合、必ずNとN-1が条件を満たすため、先に答えに加算しておく。
Nが2の場合、N-1=1となるため、条件を満たさないことに注意。(問題文をよく読もう)

あとは約数列挙して条件を満たすか確認すれば良い。

// 最初に操作1をn回行ったのち、操作2をm回行うことによってNを1にできるかどうかを判定
bool judge(ll i, ll N) {
    ll n = N;
    while (n > 1) {
        if (n % i == 0) n /= i;
        else break;
    }
    if ((n-1) % i == 0) return true;
    return false;
}

void solve(long long N){
    if (N == 2) {
        cout << 1 << endl;
        return;
    }

    ll ans = 2;
    // N-Kの操作だけで1にできる数を求める
    for (long long i = 2; i * i <= N-1; ++i) {
        if ((N-1) % i == 0) {
            ans++;
            if ((N-1)/i != i) ans++;
        }
    }

    // N/Kを1回以上使って1にできる数を求める
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            ans += judge(i, N);
            if (N/i != i) ans += judge(N/i, N);
        }
    }

    cout << ans << endl;
}