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

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

diverta 2019 D - DivRem Number (緑色, 500 点)

AtCoder AtCoder500点 数学(整数問題) 全探索 約数 最適化テク:探索候補を絞る あまりを扱うのに商を使う 緑色diff ARC-D

楽しかった

問題へのリンク

問題概要

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

  • N を m で割ったときの商と余りが一致する

制約

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

考えたこと

とりあえず N = 1, 2, \dots, 10 について手元で計算しているうちに、商と余りとが一致した値 r として考えられるものは \sqrt{N} くらいの大きさにならないことが見えてきた。具体的には

  • N ÷ m = r ... r

となったときに、余りの定義から m > r なので N = mr + r \gt r^{2} という感じになる。よって r = 1, 2, \dots, \sqrt{N} くらいまで試せば OK。

計算量は O(\sqrt{N})。

#include <iostream>
#include <vector>
using namespace std;

long long solve(long long N) {
    long long res = 0;
    for (long long r = 1; r*r <= N; ++r) {
        if ((N-r) % r == 0 && (N-r)/r > r) res += (N-r)/r;
    }
    return res;
}

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

直接的に求める

さらに直接求めることもできて、

  • N = mr + r = (m+1)r

と表せるので、

  • r は N の約数である
  • r \lt m であってこれは r^{2} + r \gt N と同値である

ということがわかる。したがって

  • N の約数 r を列挙して
  • そのうち r^{2} + r \lt N を満たすものについて
  • (N-r)/r を合計する

としてもよい。ここで、 r が int 型にもおさまらないような値だと r^{2} + r を計算すると 64 bit 整数にもおさまらないことが気になるが、 r \gt 10^{6} とかだと r^{2} + r \gt 10^{12} になることから r^{2} + r \gt N とはなりえないことを利用して弾くことができる。

計算量は約数計算がボトルネックで、やは O(\sqrt{N})。

#include <iostream>
#include <vector>
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) {
    auto div = calc_divisor(N);
    long long res = 0;
    for (auto r : div) {
        if (r > 1000000) continue;
        if (N > r*r + r) res += (N-r)/r;
    }
    return res;
}

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