AtCoder Beginner Contest 112 D - Partition

問題

atcoder.jp

考察と解法

まずはじめに、すべてのがすべてのの最大公約数で割り切れることに気づきました(それはそう)。
を満たすの最大公約数をとするとであるから
自然数を用いて

(式1)

となり、はMの約数であることがわかります。
したがって、Mの約数をすべて列挙し、(式1)のに代入して満たすか確認すればよいです。 しかし、が最大公約数でなくても、公約数であるなら(式1)を満たすことがわかります。
例えば、の場合を考えると

となりの2つの場合があることがわかります。 (式1)を満たすをすべて求めて最大のものが真のとなるため、この場合はが解になります。 また、はMの約数でありながらでは(式1)を満たすことはできません。 この理由は、(式1)を以下のように変形するとわかります。

xはMの約数なので右辺は必ず整数値になります。 が自然数であるという制約から

(式2)

となり、では(式2)を満たさないため、条件を満たすを構成することができません。 逆に(式2)を満たすなら、とすることでを構成することができます。

以上のことをまとめると以下のアルゴリズムでこの問題を解くことができます。

アルゴリズム

1. Mのすべての約数を列挙する
2. Mの約数の中から(式2)を満たすxをすべて調べる
3. 2で調べたxの中で最大のものを解とする

計算量

1の処理がO()
2の処理が多く見積もってO()
3は2を行う中で最大値を更新すればよいため、O(1)

1, 2の処理は独立しているため、全体の計算量はO()

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, m, gcd = 1;
    vector<int> divisor;
 
    cin >> n >> m;
 
    for(int i = 1; i * i <= m; ++i)
    {
        if(m % i == 0)
        {
            divisor.push_back(i);
            divisor.push_back(m / i);
        }
    }
 
    for(int i = 0; i < divisor.size(); ++i)
    {
        if(m / divisor[i] >= n)
        {
            gcd = max(gcd, divisor[i]);
        }
    }
 
    cout << gcd << endl;
}

感想

数学っぽい問題が本当に苦手なので解けて嬉しいです。