ABC108-C：Triangular Relationship
問題
https://beta.atcoder.jp/contests/abc108/tasks/arc102_a
が与えられる。
以下の整数の組
で
がすべて
の倍数であるような組の個数を求めよ。
制約
考え方
一つの変数を全探索することを考える。 について
で
の範囲を全探索する。
が定まると
はそれぞれ
と一意に決まる。そのときに
が満たされていれば良い。
あらかじめ の範囲に含まれる
の個数を求めておけば、全探索したときのそれぞれについて
で求めることができるので全体の計算量は
で解が求める。
Submission #3751671 - AtCoder Beginner Contest 108
どこに着目して考察するべきだったか
つの変数までは全探索できることを考える。また与えられている条件は
上の演算になることから
について
で考えることに気づく。
何がバグっていたか
得た知見
mod 上で考えるとうまくいくことがある