CF1056B Divide Candies

Arkady 和他的朋友们喜欢在一个 $n \times n$ 的棋盘上玩跳棋。棋盘的行和列编号从 $1$ 到 $n$。 最近朋友们赢得了一场锦标赛，所以 Arkady 想用一些糖果来奖励他们。Arkady 记得一个古老的寓言（但不记得寓意），他想为棋盘上的每一个格子都准备一份糖果：对于格子 $(i, j)$，他会准备恰好 $i^2 + j^2$ 颗独特类型的糖果。 共有 $m$ 个朋友值得获得奖励。问在这些 $n \times n$ 份糖果中，有多少份可以被平分成 $m$ 份且每份糖果都是完整的？注意，每一份糖果都需要独立分配，因为不同格子的糖果类型各不相同。

一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^9$，$1 \le m \le 1000$），分别表示棋盘的大小和需要分成的份数。

输出一个整数，表示可以被平分的糖果份数。

在第一个样例中，只有格子 $(3, 3)$ 的糖果可以被平分（$3^2 + 3^2 = 18$，可以被 $m=3$ 整除）。 在第二个样例中，以下格子的糖果可以被平分： - $(1, 2)$ 和 $(2, 1)$，因为 $1^2 + 2^2 = 5$，可以被 $5$ 整除； - $(1, 3)$ 和 $(3, 1)$； - $(2, 4)$ 和 $(4, 2)$； - $(2, 6)$ 和 $(6, 2)$； - $(3, 4)$ 和 $(4, 3)$； - $(3, 6)$ 和 $(6, 3)$； - $(5, 5)$。 在第三个样例中，所有格子的糖果都可以被平分，因为 $m = 1$。 由 ChatGPT 4.1 翻译