問題
異なる正の整数の集合に対して、どの
についても
と
のその他の要素の和の最大公約数が1でないとき特別であるということとする。要素数
の特別な集合であり、全ての要素の最大公約数が1であり、どの要素も30000以下であるものを求めよ。
解法
1時間半ほど考えたがわからなかったので解説PDFを読んだ。
が6の倍数であり、
が全て2か3の倍数の倍数であれば特別となる。そして2と3を含むとき全要素の最大公約数が1となるため条件も満たされる。
が2か3の倍数であることは、6で割ったあまりが0,2,3,4のどれかだということなので、30000までの正の整数の
、つまり20000個は存在するため十分にある。
2か3の倍数である整数を小さいほうから個取っていき、和を計算する。すでに6の倍数であればそのまま出力良いため、そうでない場合を考える。
mod 6において0, 2, 3, 4, 0, 2, 3, 4 ... と取っていくため、和を6で割った余りとしてありえるのは0, 2, 5, 3, 3, 5, 2, 0, 0 ...であり、つまり0, 2, 3, 5の4通りである。
余りが2の時は、取った整数列の中から6で割った余りが2であるものを一つ取り除き、6で割った余りが0であるものを一つ追加すればよい。ほかの場合も同様に一つ取り除いて一つ追加することで上手く和を6の倍数にできる。
取り除くものが必ず取れるようにが小さいケースは特別に処理すれば、上記の操作によって解ける。
反省
以前解説を読んだときのおぼろげな記憶により、30000という数字が重要であるということは思い出した。そしての制約との関係からおおよそ
取れれば良いことには気づき、3の倍数の余りに着目してそのうち二つを取るなどということを考えていた。
しばらくして"特別"となる条件のために偶奇性も考えたほうが良さそうとなり、6の倍数の余りが0, 2, 3, 4であるものに着目するところまでは気が付いた。しかしそれぞれの数を個,
個,
個,[tex;N - i - j - k]個と置いてループを回すと計算量が大きすぎる……というところでずっと詰まってしまった。和についても6の倍数になっているかどうかを考えるという方向に行っていないため、考察としては良くなかった。
教訓としては、制約を見て割合を確認→余りに着目という感じだろうか。600点問題の中では結構難しいほうだと感じた。
コード
かなり愚直に解説をコードに落としただけ。長いのでリンクで。
