問題
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-k
はmk-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; } }