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

問題概要

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