arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC112 D - Partition を解いてみた

問題リンク

atcoder.jp

問題概要

 N M が与えられる。
正整数からなる長さ  N の数列  a a _  1 + a _  2 + \cdots + a _  N = M を満たす場合の 数列  a の最大公約数のとりうる最大値を求めよ。

制約

1 \leq N \leq 10 ^ 5
N \leq M \leq 10 ^ 9

ポイント

  • 数列  a の最大公約数を  x とすると  M = a _  1 + a _  2 + \cdots + a _  N x で割り切れるため、 x M の約数である。
  • 従って求める最大公約数は  M の約数の中にある。
  • 約数列挙は  O(\sqrt{M}) で求められ、あとは約数の値で全探索を行う。
  • とりあえず  a_ i をすべて  x とすると数列の和は  n \times x となる。これが  M を超えていると当然不可。逆に  M 以下の場合は、 M - n \times x の差分は  x の倍数であり、この差分を適当な  a_ i に押し付けることで、数列の最大公約数が  x かつ  a _  1 + a _  2 + \cdots + a _  N = M を満たすことができる。
  • まとめると、 M の約数 かつ  n \times x \leq M の最大値を求めればよい。

感想

Mの約数の中に存在することに気付けるかが大事でしたね。実装は軽め。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

vector<ll> enum_divisors(ll N) {
  vector<ll> res;
  for (ll i = 1; i * i <= N; ++i) {
    if (N % i == 0) {
      res.push_back(i);
      if (N/i != i) res.push_back(N/i);
    }
  }
  // 降順にソートする
  sort(res.begin(), res.end());
  reverse(res.begin(), res.end());
  return res;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> vec = enum_divisors(m);
  for (auto x : vec) {
    if (x*n > m) continue;
    cout << x << endl;
    return 0;
  }
  return 0;
}