← 返回题目列表

Codeforces · 1056/B

B. 划分糖果

中文机器翻译题面 查看原题

Arkady 和他的朋友们喜欢在 $$$n \times n$$$ 的场地上玩跳棋。该字段的行和列从 $$$1$$$ 到 $$$n$$$ 进行枚举。

朋友们最近赢得了冠军,所以阿尔卡迪想用一些糖果来取悦他们。记得一个古老的寓言(但不是它的寓意),阿尔卡迪想给他的朋友场上每个单元格一组糖果:单元格 $$$(i, j)$$$ 的糖果组将恰好有 $$$(i^2 + j^2)$$$ 独特类型的糖果。

有 $$$m$$$ 朋友值得这份礼物。这些 $$$n \times n$$$ 组糖果中有多少可以平均分成 $$$m$$$ 部分而不需要将糖果切成碎片?请注意,每组必须独立拆分,因为不同组中的糖果类型不同。

输入

唯一的行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 1000$$$) - 字段的大小和将集合分割成的部分的数量。

输出

打印一个整数——可以平均分割的组数。

示例

输入 #1

3 3

输出 #1

1

输入 #2

6 5

输出 #2

13

输入 #3

1000000000 1

输出 #3

1000000000000000000

注意

在第一个示例中,只有单元格 $$$(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$$$。