2803: T4-欲擒故纵
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
33DAI 和 Kitten 在玩一款战争游戏。但 33DAI 没有着急立马去进攻，而是姑且先让 Kitten 轻松一下，33DAI 准备先采取一种奇怪阵法来形成战斗力。
这套阵法有一个战斗力系数 $k$，最终战斗力和士兵数量息息相关：
- 如果士兵数量为 $1$ 则战斗力就是 $1$。
- 假设有 $n$（$n\gt 1$） 名士兵
- 先需要把士兵平分成 $x$ 个小组。这里 $x$ 必须大于 $1$、必须是 $n$ 的因子（不然怎么叫平分）、且必须是所有满足前面条件的数中最小的一个。
- 因为是平分，此时每个小组的人数都是 $\frac{n}{x}$。最终战斗力就是所有小组用同样战斗力系数算出的战斗力之和再乘以 $k$ 再对 $10^9+7$ 取模后的结果。
由此，**在不考虑整型溢出**的情况下，可以用下面这个递归程序，算出 $n$ 名士兵，战斗力系数为 $k$ 时的最终战斗力（显然在战斗力超过 `int` 范围时计算会错误）。
现在 33DAI 想要分析所有人数下的战斗力，对于整数 $m,k$，他希望算出以 $k$ 为战斗力系数时，$1$ 名士兵到 $m$ 名士兵战斗力分别是多少。为了避免大量输出，他只需要你算出这些战斗力的异或和即可。
在**不考虑超时和整型溢出**的情况下，把上面代码的主函数改成下面这段即可得到正确的结果。
但显然，我不会给这个代码分数的，这里只是为了让你更好理解题意。
这套阵法有一个战斗力系数 $k$，最终战斗力和士兵数量息息相关：
- 如果士兵数量为 $1$ 则战斗力就是 $1$。
- 假设有 $n$（$n\gt 1$） 名士兵
- 先需要把士兵平分成 $x$ 个小组。这里 $x$ 必须大于 $1$、必须是 $n$ 的因子（不然怎么叫平分）、且必须是所有满足前面条件的数中最小的一个。
- 因为是平分，此时每个小组的人数都是 $\frac{n}{x}$。最终战斗力就是所有小组用同样战斗力系数算出的战斗力之和再乘以 $k$ 再对 $10^9+7$ 取模后的结果。
由此，**在不考虑整型溢出**的情况下，可以用下面这个递归程序，算出 $n$ 名士兵，战斗力系数为 $k$ 时的最终战斗力（显然在战斗力超过 `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 想要分析所有人数下的战斗力，对于整数 $m,k$，他希望算出以 $k$ 为战斗力系数时，$1$ 名士兵到 $m$ 名士兵战斗力分别是多少。为了避免大量输出，他只需要你算出这些战斗力的异或和即可。
在**不考虑超时和整型溢出**的情况下，把上面代码的主函数改成下面这段即可得到正确的结果。
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;
}
但显然，我不会给这个代码分数的，这里只是为了让你更好理解题意。
输入
两个整数，$m,k$。
输出
一个整数，即答案。
样例输入 复制
1 33样例输出 复制
1提示
`f(1,33)=1`
```input2
5 2
```
```output2
25
```
`f(1,2)^f(2,2)^f(3,2)^f(4,2)^f(5,2)` 的值是 `25`。更多的样例就不给了，大家可以自己用上面的代码片段组合起来自己造样例。
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le m \le 2\times 10^7$，$1\le k\le 100$。
- 子任务 1（10 分）：保证 $k=1$。
- 子任务 2（20 分）：保证 $m\le 10^4$。
- 子任务 3（30 分）：保证 $m\le 10^6$。
- 子任务 4（40 分）：没有特殊限制。
```input2
5 2
```
```output2
25
```
`f(1,2)^f(2,2)^f(3,2)^f(4,2)^f(5,2)` 的值是 `25`。更多的样例就不给了，大家可以自己用上面的代码片段组合起来自己造样例。
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le m \le 2\times 10^7$，$1\le k\le 100$。
- 子任务 1（10 分）：保证 $k=1$。
- 子任务 2（20 分）：保证 $m\le 10^4$。
- 子任务 3（30 分）：保证 $m\le 10^6$。
- 子任务 4（40 分）：没有特殊限制。