はまやんはまやんはまやん

hamayanhamayan's blog

Partition [AtCoder Beginner Contest 112 D]

https://beta.atcoder.jp/contests/abc112/tasks/abc112_d

解法

https://beta.atcoder.jp/contests/abc112/submissions/3348509

全ての要素の公約数としてgがある場合を考える。
全ての要素がgの倍数になれば、公約数がgになる。
まず、満たすべき条件としてMがgで割り切れる必要がある。
M/g個のgを各要素に分配していくことを考えるが、各要素最低1つは割り当てられる必要がある。
よって、N≦M/gが満たされる必要がある。
 
公約数gを全探索するが、これはMの約数になっているので、そんなに量がない。
約数gのうち、N≦M/gを満たす最大のgが答え。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    auto ed = enumdiv(M);
 
    int ans = 1;
    fore(d, ed) if (N <= M / d) ans = d;
    cout << ans << endl;
}