Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

B. Omkar and Last Class of Math (Codeforces Round #655 Div. 2)

問題

https://codeforces.com/contest/1372/problem/B

問題概要

正数nが与えられる。以下の条件を満たす正数の組{a, b}を答えよ

  • a + b = n
  • 上記の条件を満たすa, bのうちでlcm(a, b)が最も小さい

考察(証明)

あるn未満の正数kをとってきて、a=k, b=n-kとおきます。ここでk<=n-kとしてよいです。(そうでなければ入れ替えればよいため)

kがnの約数の時、n-kはkの倍数です。kがnの約数であるなら、mk=nとなるような整数mが存在して、n-kmk-k = n-kより(m-1)k = n-kと表すことができるからです。 よってこの時n-kはkの倍数であることが示されたので、lcm(k, n-k)n-kとなります。

一方kがnの約数でない時、n-kはkの倍数ではなく、lcm(k, n-k)は少なくともn-kより大きな数となります。具体的には2(n-k)以上の数となり、これは明らかにn以上の数となります。(前提条件よりn-kはn/2以上の数であり、その2倍はn以上です)

これらにより、lcmがより小さくなるのはkがnの約数の時であることがわかりました。ここでlcm(k, n-k)n-kであることから、n-kを最小化しなければなりませんが、これはkを最大化すればよく、最大のkは、(nを除く)nの約数の中で最大のものであるので、それがaとなり、bはn-aとすればよいことがわかります。

#include <bits/stdc++.h>
using namespace std;
 
vector<long long> divisors(long long n) {
    vector<long long> v;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            if (i * i != n) {
                v.push_back(n / i);
            }
        }
    }
    return v;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        auto d = divisors(n);
        sort(d.begin(), d.end());
        int m = d.size();
        // この実装では、列挙した約数にn自身が含まれているので、ソートして最後から2番目の数を取るのが適切
        cout << d[m - 2] << " " << n - d[m - 2] << endl;
    }
}