AGC022B
https://gyazo.com/13f3d39471baeb131d387b0805df3eab
考えたこと
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」も満たされる