No.97

$N$ が小さい場合と大きい場合で場合分けする.

$N$ が小さい場合は愚直に計算すればいい.

$N$ が大きい場合は, ${ aq_i }$ も一様に分布すると考えられるので, 答えも大きくなる可能性が高い.

答えを $m$ とすると,

$$m = aq_i \Longleftrightarrow a = mq^{-1}$$

となるので, $q$ の逆元を計算して $m$ が大きい順に $mq^{-1}$ を計算して $A$ に含まれるかどうかを調べる.

$N$ が小さい場合と大きい場合のしきい値は愚直計算でも TLE にならないように適当に決める.