Codeforces Round #613 (Div. 2) - C. Fadi and LCM
概要
Xが与えられる。lcm(a, b)=Xを満たすような(a, b)の組のうち、max(a, b)を最小化せよ。
制約： 1 <= X <= 10^12
ACするまで
1. aとbはできるだけ近くないといけないとわかる。でも、どうやって？
2. 「最大値の最小化」と二分探索のにおいがぷんぷんするものの、これは割り切れるかどうかは連続ではないので二分探索ではない。
3. LCMとGCDにまつわる典型テクニック、互いに素で攻めてみる。
4. それで考えると、互いに素の性質を利用した全探索が間に合うとわかる。AC
考察
GCDとLCMの問題で、次のようなテクニックがあるといえる。
Point
GCDとLCMの問題は、互いに素ならばどうなるか？が突破口になりうる。
今回の場合、これで考えてみる。
aとbが互いに素でないとき、a = gp , b = gq (g, p, qは自然数)として、X = lcm(a, b) = gpq となる。この時、aとbのうち、大きい方からgを割れば、max(a, b)を現状維持、もしくは小さくすることができる。
この作業を続けると、aとbは最終的に互いに素になる。
しかし、どの素因数をa or bに振り分けるのか、これは一概には言えず、コンピューター特有の全探索的手法で探るしかない。
最後に計算量解析を載せる。
オーバービュー用要約
Point
GCDとLCMの問題は、互いに素ならばどうなるか？が突破口になりうる。
一言
これは本当に猛反省すべき。
