#D. 欲擒姑纵

    传统题 文件IO:yu 1000ms 256MiB

欲擒姑纵

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

逼则反兵,走则减势。紧随勿迫,累其气力,消其斗志,散而后擒,兵不血刃。需,有孚,光。

题目描述

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

这套阵法有一个战斗力系数 kk,最终战斗力和士兵数量息息相关:

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

由此,在不考虑整型溢出的情况下,可以用下面这个递归程序,算出 nn 名士兵,战斗力系数为 kk 时的最终战斗力(显然在战斗力超过 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,km,k,他希望算出以 kk 为战斗力系数时,11 名士兵到 mm 名士兵战斗力分别是多少。为了避免大量输出,他只需要你算出这些战斗力的异或和即可。

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


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,km,k

输出格式

一个整数,即答案。

1 33
1

f(1,33)=1

5 2
25

f(1,2)^f(2,2)^f(3,2)^f(4,2)^f(5,2) 的值是 25。更多的样例就不给了,大家可以自己用上面的代码片段组合起来自己造样例。

数据规模与约定

对于 100%100\% 的数据,1m2×1071 \le m \le 2\times 10^71k1001\le k\le 100

  • 子任务 1(10 分):保证 k=1k=1
  • 子任务 2(20 分):保证 m104m\le 10^4
  • 子任务 3(30 分):保证 m106m\le 10^6
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第十场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-3 4:00
结束于
2024-10-5 4:00
持续时间
3.5 小时
主持人
参赛人数
88