-
1: すべてのgcdは1
-
2: ある一つと、それ以外の和の、gcdは1でない
-
3: 要素は30000以下
-
うーむ、イメージが湧かないが条件2から、1は要素になれないな
-
2があるなら、一つ以上の奇数が存在する。また2以外を足したものは偶数。
-
サイズ2の解がないことは容易に示せる
-
3の時を考える
- 2があるなら残り二つは奇数
- 3があるなら残りは3n+1
- 奇数であって、3n+1であって、5の倍数なもの
- 25だな
- よって2,3,25は解
-
4の時を考える
- 残り3つに偶数が1つ
- 3があるなら残り2つの和は3n+1
- 5があるなら残り一つは5m
- うーむ、場合分けがたくさんになるぞ
-
2+3+25=30=2×3×5だな
- 2×3×5×7=210をうまく分配…どうやって？
-
制約を厳しく考えすぎてる
- 全部のgcdが1である条件は、2×3, 3×5, 5×2でも成立する
- でもこの例だと条件2が無理だな
-
条件1がない場合
- 簡単、全部偶数とかでOK
- 条件1を満たすために奇数を2つ入れる
- 奇数以外については条件2が成り立つ
- この奇数に条件2が成り立つためには？
- 奇数の素数で、双方に共通するものが必要
- 二つの奇数をa,b,偶数の和をcとする
- a+cとb、b+cとaに共通の約数が必要
- この二つの約数が一致すると条件1が壊れるのでダメ
- a=3n, b=5mとしたら？
- 問題なく見つかりそうな気がするがコードを書いて確認したい
- cは3や5の倍数ではダメだが、偶数であればいいので適当に調整すればよい
- cの3や5での剰余が決まればaやbのも決まる
- 中国剰余定理で30までに条件を満たす数があることが保証される
-
公式解説
- 制約の厳しさを見落としていた
- 要素30000以下で20000個選ぶなら「ほとんど偶数」という選択肢は取れない
- 僕が「合計は2の倍数」と仮定して40000ぐらいまでの数で構成する方法を導いた
- これを「合計は2と3の倍数」とするのが公式解説手法
- 合計が2と3の倍数であり、構成要素が2または3の倍数であれば「2: ある一つと、それ以外の和の、gcdは1でない」が満たされる
- 2と3が構成要素に入っていれば「1: すべてのgcdは1」も満たされる
- 制約の厳しさを見落としていた