AtCoder ABC 161 F - Division or Substraction (水色, 600 点)

めちゃくちゃ面白かった！！！

問題へのリンク

問題概要

整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。

• 整数 を用いて、 に対して操作を行っていく
• が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える。
• 上記の操作を が 未満になるまで繰り返したとき、 は となる

制約

• 

考えたこと

問題文を読んでも状況がパッとつかめない。こういうときは幾つかのケースを手で試すと良さそうである。 のときは、こんな感じになる。

K	変化	結果
2	22 → 11 → 9 → 7 → 5 → 3 → 1	o
3	22 → 19 → 16 → 13 → 10 → 7 → 4 → 1	o
4	22 → 18 → 14 → 10 → 6 → 2	x
5	22 → 17 → 12 → 2	x
6	22 → 16 → 10 → 4	x
7	22 → 15 → 8 → 1	o
8	22 → 14 → 6	x
9	22 → 13 → 4	x
10	22 → 12 → 2	x
11	22 → 2	x
12	22 → 10	x
13	22 → 9	x
14	22 → 8	x
15	22 → 7	x
16	22 → 6	x
17	22 → 5	x
18	22 → 4	x
19	22 → 3	x
20	22 → 2	x
21	22 → 1	o
22	22 → 1	o

ここから読み取れることは

• が の約数でないときは、最終的には % が残る
• が の約数のときは、 を で割れるだけ割った値を として、 % が残る

といったことだ。場合分けして考えてみよう。

が の約数でないとき

を で割ったあまりが 1 になればよいのだ。つまり、

あまり
⇔

という風になればよい。これは、 が の約数であることを意味するのだ。よりちゃんというと、以下の条件を満たすことが必要十分条件である！！！

---

• が の約数
• 

---

注意点として、もしこれが「 を で割ったあまりが になるような を求めよ」という問題だった場合には、こういう風になる。

• が の約数
• 

「あまりは割る数より小さくなければならない」という見えない制約に注意する。今回はあまりが 1 なので、深く気にしなくても大丈夫。

が の約数であるとき

そもそも の約数の個数が少ないので、これはもう全て試してしまうのがわかりやすいと思う。

まとめ

以上をまとめると、答えは以下を合わせたもの

• の約数のうち、 を除外したもの
• の約数はすべて調べ尽くす

なお、前者と後者は被ることはない ( と は互いに素)。計算量は となる。

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

vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

long long solve(long long N) {
    const auto &div1 = calc_divisor(N-1);
    const auto &div2 = calc_divisor(N);
    long long res = (int)div1.size() - 1; // 1 を除外
    for (auto d : div2) {
        if (d == 1) continue;
        long long NN = N;
        while (NN % d == 0) NN /= d;
        if ((NN-1) % d == 0) ++res;
    }
    return res;
}

int main() {
    long long K;
    while (cin >> K) cout << solve(K) << endl;
}