(82)平方数のp^2での余りの個数を数えたい

こんばんは。今日は2012年の東大オープンの問題を解説します。

これは発想は自然だけど書くのに苦労しました。激易って嘘だろ。易くらいだろ。

発想は簡単で、pで割った余りの個数はすぐでて、あとは(ap+k)^2のp^2で割ったあまりを考えたら2apの部分で余り調節ができて数が数えれそうってなります。