2022-07-22 AGC022 の B を解いた
AGC022 : AtCoder Grand Contest 022 の B を解いた。
- B - GCD Sequence
https://atcoder.jp/contests/agc022/tasks/agc022_b
- 提出: https://atcoder.jp/contests/agc022/submissions/33408953
- 解説 AC
- 素数を列挙して……かと思ったけど
N <= 20_000でa_i <= 30_000なので厳しい gcd(S) = 1は 2, 3 を含めれば良さそうgcd(a_i, sum(S) - a_i) != 1をどうするか 6 (2 と 3 の両方) の倍数になれば良い ?- このあたりで断念
gcd(a_i, sum(S) - a_i) != 1はgcd(a_i, sum(S)) != 1で良い- a_1 (=2), a_2 (=3) 以外を 6 の倍数 (mod 6) で考えると 0..6 のうち 0, 2, 3, 4 で 4/6 はとれるので 30_000 で 20_000 がとれそう
- 先頭から列挙すると、 2, 3, 4, 6, 8 (6+2), 9 (6+3), ... と続く
- 1 周期未満は調整が効かないのでなんとかする
3 <= N < 6(1 周期未満) のうち 3, 4 は入力例から取れる- 5 は 2, 5, 20, 63 から手計算で 2, 5, 20, 30, 63 が求められる
- 1 周期以上ある場合は調整が効く。和として出てくるのは 0, 2, 3, 5 (mod 6)
- 0 は何もしなくて良い
- 2 なら 2 ( 1 周期分はあるので 8 (6+2) を除く) を除いて次の 0 を加えると 0 になる
- 3 なら 3 ( 1 周期分はあるので 9 (6+3) を除く) を除いて次の 0 を加えると 0 になる
- 5 なら 3 ( 1 周期分はあるので 9 (6+3) を除く) を除いて次の 4 を加えると 0 になる
- 30_000 はギリギリなので次の周期ではみ出さないように注意する
今日のコミット。