[Codeforces] Round #535 B. Divisors of Two Integers

Divisors of Two Integers

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

考え方

題意

\( x \) の約数と \( y \) の約数のリスト \(d\) が与えらえれたとき、 自然数 \( x, y\) を答える問題です。

方針

\( x \leq y \) として考えます。\( d \) を昇順に整列させたとき、\( y = d_n\) となることが分かります。また、\( d_{n – 1} = d_n \) のとき、\( x = y \) となります。

\( d \) の要素の中で同じ値が二つあるものが \( x \) の候補となるので、その値の最大値を\( x_1 \) とします。また、\( y \) の約数ではない値も \( x \) の候補となります。その値の最大値を \( x_2 \) とすると、\( x = \max(x_1, x_2) \) となります。

コード

感想

二つ条件を考えないといけないのが難しかったです。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする