DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選：C - ロト2
問題
https://atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_c
なる
の組を求める問題。
考え方
単純に では間に合わないので工夫が必要である。数学をするのだが、以下の式が成り立つ。
直感的には は
の素因数のみが
の倍数に寄与するので最大公約数
をとったとしても結果に影響はない...というイメージである。
の最大公約数をとることができると各
について同じ数をまとめて数えることができる。
の約数の個数は十分小さいので全探索できる。
Submission #4144425 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選
どこに着目して考察するべきだったか
何がバグっていたか
得た知見(典型ポイント)
- 個数をまとめて計算
- 要素数をまとめて全探索
- 倍数判定の言い換え
