F – Division or Substraction 解説 (AtCoder Beginner Contest 161)

2020年4月5日AtCoder剰余,約数,600点,互いに素

問題へのリンク

問題概要

\(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。

  • \(N\) が \(K\) で割り切れる：\(N\) を \(\frac{N}{K}\) にする
  • \(N\) が \(K\) で割り切れない：\(N\) を \(N-K\) にする

制約

  • \( 2 \leq N \leq 10^{12}\)

考え方

操作が2つある時は、同時に考えると分かりにくいのでそれぞれ状況を分けて考えてみるとわかりやすくなります。

\(N\) が \(K\) で割り切れない時

\(N\) が \(K\) で割り切れない時は、 \(N\) を \(K\) で引き続けることになります。

少し実験してみるとわかりますが、何回操作したとしても、\(N\) が \(K\) で割り切れるようになることはありません。

これは \(N ~mod K\) の値が常に一定となるからです。

ここから考えると、最後に 1 になるのは \(N ~mod K\) の値が 1 になる時であると分かります。\(N-1\) の約数（ただし 1 以外）であれば、この条件を満たします。

\(N\) と \(N-1\) は互いに素であるので、\(N-1\) の約数 k で \(N\) を割り切れることはありません。（つまり、「\(N\) が \(K\) で割り切れる時」と被ることはありません。）

\(N\) が \(K\) で割り切れる時

\(N\) が \(K\) で割り切れるのは、\(K\) が \(N\) の約数の時です。操作をしていって最終的に 1 になるかどうかは実際に試してみれば良いです。

問題を解くだけなら、以上のことがわかっていれば良いですが、もう少し詳しく考察してみます。

\(N\) を \(K\) で \(a\) 回割った後に、\(b\) 回引くことになった場合を考えてみます。最終的に 1 になる場合は以下の式が成立します。

\begin{align}
\frac{N}{K^a} – bK = 1 \\
\frac{N}{K^a} = 1 + bK\\
\frac{N}{K^a} – 1 = bK
\end{align}

つまり、 \(\frac{N}{K^a} – 1\) を \(K\) で割り切れるかどうか判定すれば良いです。

ですが、実際に操作をシミュレートしてみるほうが考えやすいと思います。

解法

答えは以下の数の和

  • N-1 の約数の数（1は除く）
  • N の約数 K について、「\(\frac{N}{K^a} – 1\) を \(K\) で割り切れるか数える」 or 「実際にシミュレートして 1 になるものを数える」

計算量

  • \(O(\sqrt{N})\)

\(N\) と \(N-1\) の約数を求めるのに一番時間がかかるので、計算量は \(O(\sqrt{N})\) です。

C++での実装例

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;

/*  divisor(n)
    入力：整数 n
    出力：nのすべての約数
    計算量：O(√n)
*/
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}

using ll = long long;

int main() {
    ll N;
    cin >> N;
    ll ans = 0;

    // K で割り切れない時
    auto div = divisor(N - 1);
    ans += (int)div.size() - 1;

    // K で割り切れる時
    auto dv = divisor(N);
    for (auto k : dv) {
        if (k == 1) continue;
        ll n = N;
        while (n % k == 0) {
            n /= k;
        }
        if (n % k == 1) ans++;
    }

    cout << ans << endl;
}

AtCoder剰余,約数,600点,互いに素