AGC 022 B - GCD Sequence
問題概要
サイズN, 各要素が30000以下の次の条件を満たす数列を求めよ.
- 全ての要素のgcdは1である(全ての要素が互いに素ということではない)
- 全要素の和をSとして,全てのiに対して gcd(a_i, S-a_i) != 1
解法
gcd(a_i, S-a_i) != 1 <-> gcd(a_i, S) != 1
それぞれ二つの異なる素数x,yを因数に含む二つのグループから数列を構成することを考える.
{x,2x,3x,...} + {y,2y,3y,...} (もし等しい要素ができてしまった場合は省く)
x,yは異なる素数だから全てのgcdは1となる.
次に二つ目の条件を考えると, {x,2x,3x,...}の和がyの倍数に,{y,2y,3y,...}の和がxの倍数になれば
S=0 mod xyとなり,全ての要素について条件を満たすことがわかる.
また制約から考えるとx=2,y=3でなければならず,実際に30000以下では |(2の倍数)or(3の倍数)| = 20000である.
よって,
(1) 3,6,9,12,15,... を和が偶数になるように,
(2) 2,4,8,10,14,16,...(偶数)(3の倍数) を和が3の倍数になるように並べれば良い.
(1)で和のmod2について注目すると,+1,0,+1,0,..から,(個数) = 0,3 (mod 4)がわかる.
(2)も同様にmod3で+2,+1,+2,+1,...から, (個数) = 0 (mod2)
よって奇数であれば 5 -> 3+2, 7 -> 3+4, 9 -> 7+2, 11 -> 7+4,..
偶数であれば 6->4+2, 8->4+4, 10->8+2, 12->8+4,...
と個数を振り分けていく.
上限が30000なので,(1)の個数は10000以下であることに注意する.
個数がわかればその個数分だけ出力していけば良い.
このやり方ではN=3,4だとできないのでそこはサンプルケースを埋め込むことにも注意する.
メモ
考察があやふやなまま実装してしまったので,N=19999,20000あたりのケースで死んだ.
また,2グループに分けるところにたどり着くまでの考察も致命的に遅かった.
制約からのエスパーもできるべきぐらいのわかりやすさだったかなと思う.
