この問題の入力は、正の整数と単一の正の整数 k の配列 A です。プログラムの出力は、k が以下で定義されたセット S にある場合は True、そうでない場合は False です。
セット S を次のように定義します。
- x が A にある場合、x は S にある
- x と y が S にある場合、GCD(x,y) は S にある
- x と y が S にある場合、LCD(x,y) は S にある
追加の制約: 配列 A のサイズは ≤ 50000、k ≤ 10 12、および A の各 x について x ≤ 10 12です。プログラムは 1 秒以内に答えを返さなければなりません。
いい考えがありません。私が考えることができる唯一のことは、配列内の整数の任意のペアの GCD と LCM を見つけることです。その後、集合 S を拡大できます。 .
皆さんが私を助けてくれることを願っています。私はこれに長い間立ち往生しています。
アップデート：
たとえば、配列は A= { 10, 12, 15 } です。
前述したように、S = {..., 10, 12, 15, ...}
10、12、15 は S にあることがわかっています。したがって、それらの GCD と LCM も S にあります。つまり:
S で GCD(10, 12) = 2
S で GCD(10, 15) = 5
S で GCD(12, 15) = 3
LCM(10, 12) = S で 60
...
ついに：
S = { 1, 2, 3, 5, 10, 12, 15, 30, 60 }