3933: 欲擒姑纵(挖土机 CSP-J 模拟赛 ~ 第十场)

33DAI 和 Kitten 在玩一款战争游戏。但 33DAI 没有着急立马去进攻，而是姑且先让 Kitten 轻松一下，33DAI 准备先采取一种奇怪阵法来形成战斗力。

这套阵法有一个战斗力系数 $�$，最终战斗力和士兵数量息息相关：

• 如果士兵数量为 $1$ 则战斗力就是 $1$。
• 假设有 $�$（$�>1$） 名士兵
  • 先需要把士兵平分成 $�$ 个小组。这里 $�$ 必须大于 $1$、必须是 $�$ 的因子（不然怎么叫平分）、且必须是所有满足前面条件的数中最小的一个。
  • 因为是平分，此时每个小组的人数都是 $\frac{�}{�}$。最终战斗力就是所有小组用同样战斗力系数算出的战斗力之和再乘以 $�$ 再对 $10^9+7$ 取模后的结果。

由此，在不考虑整型溢出的情况下，可以用下面这个递归程序，算出 $�$ 名士兵，战斗力系数为 $�$ 时的最终战斗力（显然在战斗力超过 int 范围时计算会错误）。

#include <bits/stdc++.h> using namespace std; const int MOD = 1'000'000'000 + 7; int f(int n, int k) { if (n == 1) return 1; for (int x = 2; x <= n; x++) // x>1 if (n % x == 0) // x 是 n 的因子 { // 找到第一个就停，来保证是最小的一个 int res = 0; for (int i = 1; i <= x; i++) res += f(n / x, k); return res * k % MOD; } } int main() { int n, k; cin >> n >> k; cout << f(n, k); return 0; } 

现在 33DAI 想要分析所有人数下的战斗力，对于整数 $�,�$，他希望算出以 $�$ 为战斗力系数时，$1$ 名士兵到 $�$ 名士兵战斗力分别是多少。为了避免大量输出，他只需要你算出这些战斗力的异或和即可。

在不考虑超时和整型溢出的情况下，把上面代码的主函数改成下面这段即可得到正确的结果。

 int main() { int m, k; cin >> m >> k; int ans = 0; for (int i = 1; i <= m; i++) ans = ans ^ f(i, k); cout << ans; return 0; } 

但显然，我不会给这个代码分数的，这里只是为了让你更好理解题意。

5 2

25