けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

問題概要

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

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

制約

  •  2 \le N \le 10^{12}

考えたこと

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

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

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

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

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

 K N の約数でないとき

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

 N ÷ K = q あまり  1
 N -1 = Kq

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


  •  K N-1 の約数
  •  K \gt 1

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

  •  K N-r の約数
  •  K \gt r

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

 K N の約数であるとき

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

まとめ

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

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

なお、前者と後者は被ることはない ( N-1 N は互いに素)。計算量は  O(\sqrt{N}) となる。

#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;
}