約数系の包除原理の問題として解いたけど、どう帰着するのかわからなかった。 まず lcm ではなくて最大公約数 gcd で考える。 lcm( i,k ) = i*k//gcd( i,k ) で求まる。 すると、1 ≦ i ≦ n, k なので、k の約数の集合を g とすると、g = gcd( i,k ) になる i…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

Eまで5完。Fが形式的冪級数だと気づきさえすれば６完できたのに。 Bは０が後ろにあるケースがサンプルにあったからすぐ修正できた。sort したら前から10**18 を超えたら -1 を出力するようにプログラミングしてよい。python は10**18の計算をしてもエラー吐…

4完。Eは難しかった。Dが bfs するだけなのは分かったが一から実装するのに手間取った。dfs だけライブラリとして持っていたのに... bfs も作りました。 # 木(辺のリスト作成) n, m = map(int, input().split()) g = [[] * n for i in range(n)] for i in ra…

b より大きく、a 以下の数字の積の約数の数の個数を求めればいいのだけれど、b,a が大きすぎてそのまま掛け算をするとオーバーフローする。 なので一つずつ素因数分解して、個数分だけ素数をリストに入れていって、あとで collections.Counter で数えた。 a,…

青diff 初の自力AC 解説はX = (ak/2) ∗ (2p + 1) を X が 2 で割り切れる回数と ak/2 が 2 で割り切れる回数が同じ と言い換えててあたま良すぎかとなった a のなかにひとつでも ( aj / ai )% 2 == 0 となるものがあれば答えが 0 になって、そうでないなら答…