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

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

diverta 2019 D - DivRem Number (500 点)

楽しかった

問題へのリンク

問題概要

正の整数  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;
}