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

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

AtCoder ABC 112 D - Partition (400 点)

すごく教育的ないい問題な感じ

問題へのリンク

問題概要

整数  N,  M が与えられる。
 a_1 + a_2 + \dots + a_N = M を満たす正の整数列  a_1, a_2, \dots, a_N をすべて考えたときの、 a_1, a_2, \dots, a_N の最大公約数の最大値を求めよ。

制約

  •  1 \le N \le 10^{5}
  •  N \le M \le 10^{9}

考えたこと

候補を一気に絞る

まず  a_1, a_2, \dots, a_N の最大公約数が必ず  M の約数になることがわかる。まずはここの理解が難しいかもしれない。

  •  d = {\rm GCD}(a_{1}, a_{2}, \dots a_{N}) とする
  • このとき  a_1, a_2, \dots, a_N はすべて  d の倍数である
  • よって  a_1 + a_2 + \dots + a_N d の倍数である
  • つまり  d M の約数である

こんな風に、「倍数」とか「約数」をコロコロ視点を入れ替えながら考察することがよくあるかもしれない。

あるいはこの事実を思い浮かべてもいいかも


整数  a_1, a_2, \dots, a_N が与えられて、 a_{1}x_{1} + a_{2}x_{2} + \dots + a_{N}x_{N} の形で表される整数は  {\rm GCD}(a_1, a_2, \dots, a_N) の倍数のみである


 M x_1 = x_2 = \dots = x_N = 1 とすることで表される整数なので  {\rm GCD}(a_1, a_2, \dots, a_N) の倍数でなければならない。

詰める

ここまでで、 {\rm GCD}(a_1, a_2, \dots, a_N) M の約数に絞られることがわかった。このうち最大を求めたい。あんまり大きいとダメなことがわかる。

  •  d = {\rm GCD}(a_{1}, a_{2}, \dots a_{N}) とすると、 a_i \ge d なので  Nd \le M である

ということがわかる。で、よく考えてみるとこれさえ満たしていれば、必ずそういう  a_1, a_2, \dots, a_N は作れることがわかる。

具体的には

  •  a_1 = d
  •  a_2 = d
  • ...
  •  a_{N-1} = d
  •  a_{N} = M - (N-1)d

とすればいい。

よってまとめると答えは「 M の約数  d のうち、 Nd \le M を満たす最大のものになる。

#include <iostream>
#include <vector>
#include <algorithm>
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;
}

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> div = calc_divisor(M);
    
    // M の約数 d であって、d * N <= M となる最大の d を求める
    long long res = 1;
    for (auto d : div) {
        if (d * N <= M) res = max(res, d);
    }

    cout << res << endl;
}