AtCoder Beginner Contest 112: D - Partition

競技プログラミング AtCoder 整数問題

問題

問題文

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

問題概要

整数 N, M が与えられる.

各項の和が M となる 長さ N の数列 a のうち, a の最大公約数の最大値を求めよ.

  • 1 \leqq N \leqq 10^{5}

  • N \leqq M \leqq 10^{9}

解答例

指針

  • M の約数を考える

解説

a_1, a_2, ... a_N の最大公約数を gcd(a) とすると, 数列 a の各項は gcd(a) の倍数となる.

各項が gcd(a) の倍数となり, 各項の和 M も gcd(a) の倍数となるので以下のように書ける.

a_1 + a_2 + ... + a_N = M = k \times gcd(a)

したがって, gcd(a) は M の約数となることが分かる.

k を M の約数とする

  • M = N k のとき

\overbrace{k + k + ... + k}^{N個並ぶ}= M = Nk

各項が k のとき和が M となる. このとき, a の最大公約数は k.

  • M \lt N k のとき

k + k + k ... + l \neq M \quad (l \lt k)

必ず, k より小さい項が出てくるため, k は a の最大公約数とはなり得ない.

  • M > N k のとき

k は Mの約数なので, M / k は整数となる. M / k = t とおくと条件より t > N が成り立つ.

\overbrace{k + k + ... + k}^{t個並ぶ} = \overbrace{k + k + ... + k}^{N-1個並ぶ} + (t-N+1)k = M

となり, k は a の最大公約数となり得る.

以上のことから, M の約数 k のうち M \geqq Nk であるものが解の候補となり, その中で最大のものが解となることが分かる.

約数の列挙は片方を求めるとその数で除算することでもう一方がもとまるので O(\sqrt{N}) でできる.

  • C++ による実装例
// submission: https://atcoder.jp/contests/abc112/submissions/3873615
// Language: C++14 (GCC 5.4.1)
// Time: 1 ms
// Memoly: 256 KB

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N, M, ans = 0;
    cin >> N >> M;

    for (int k = 1; k*k <= M; k++) {
        if (M % k == 0) {
            if (k <= M / N) {
                ans = max(ans, k);
            }
            if ( (M / k) <= M / N) {
                ans = max(ans, M/k);
            }
        }
    }
    cout << ans << endl;

    return 0;
}
  • Python3 による実装例
#!/usr/bin/env python3

# submission: https://atcoder.jp/contests/abc112/submissions/3873634
# Language: Python3 (3.4.3)
# Time: 24 ms
# Memoly: 3060 KB

from math import sqrt

N, M = map(int, input().split())
ans = 0

for k in range(1, int(sqrt(M)) + 1):
    if M % k == 0:
        if k <= M / N:
            ans = max(ans, k)
        if M/k <= M/N:
            ans = max(ans, M//k)
print(ans)

参考文献