首页 > 试题广场 >

many sum

[编程题]many sum

热度指数：960 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

定义序列 A ：
$A_1=$ 输入的东西~~
$A_i=(A_{i-1}+7*i) \% M, i \ge 2$
定义序列 B ： $B_i = \sum \limits_{d|i} A_d$
你要求 $\oplus _{i=1}^{N} B_i$

这样我们只要输入三个数，输出一个数啦~

其中 $\oplus$ 表示异或，也就是说你需要把所有的 $B_i$ 异或起来输出

输入描述:

第一行三个整数

输出描述:

第一行一个整数，表示答案。

示例1

输入

10 10 313

输出

备注:


通过此题的同学，不妨来想一些如果的时候该怎么做呢？（由于是小白月赛于是就删了个0)

算法知识视频讲解

C++

kilomatutinal

题解前先科普一下喵！

序列 B 的定义基于数论中的约数和：

对于每个i，B[i] = ∑ A[d]，其中d是i的所有正约数（即d能整除i）。

举个栗子喵！B[4]=A[1]+A[2]+A[4]这下就能看懂了吧

正式讲解代码了喵！

A[1]直接赋值为输入的a1。不过这里有个小细节喵：

按照题目严格来说，A[1]应该是a1！而不是a1%m喵！因为之前猫猫取的是后值，所以听取wa声一片喵~（´﹃`）
然后从i=2到n循环，用递推公式计算每个A[i]：
A[i] = (A[i-1] + 7*i) % m
每次计算完都对m取模，这样A[i]的值就在0到m-1之间啦喵～

又创建了一个数组B，大小也是n+1喵！

接下来是双重循环，这里是算法的核心喵～外层循环i从1到n，i代表一个约数喵～

内层循环j从i开始，每次增加i，直到超过n。这样j就是所有i的倍数喵～

对于每个j，我们把A[i]加到B[j]上。

这个巧妙的方法叫做“筛法”喵～它的效果是：当循环结束后，对于每个j，B[j]的值等于所有能整除j的i对应的A[i]之和。正好符合题目要求喵～（骄傲地挺胸）

先初始化ans为0，然后遍历i从1到n，用^=操作符把每个B[i]异或到ans上就完成题目啦！

上代码喵！

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    ll n,a1,m;cin >> n >> a1 >> m;
    
    vector<ll> A(n+1);
    A[1]=a1;

    for(ll i=2;i<=n;i++)
    {
        A[i]=(A[i-1]+7LL*i)%m;//A的递推公式
    }

    vector<ll> B(n+1,0);

    for(ll i=1;i<=n;i++)
    {
        for(ll j=i;j<=n;j+=i)
        {
            B[j]+=A[i];//筛法
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++) ans^=B[i];
    cout << ans;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-01-14 01:40:16 回复(3)

pypy3

_changbin

倍数分配法思路(Onlogn)

我们按 j 枚举 1~n，把 a[j] 加到所有 j 的倍数上：

j = 1 → i=1,2,3,4,5,6 加 a[1]=10
j = 2 → i=2,4,6 加 a[2]=24
j = 3 → i=3,6 加 a[3]=45
j = 4 → i=4 加 a[4]=73
j = 5 → i=5 加 a[5]=108

j = 6 → i=6 加 a[6]=150

n,a1,m=map(int,input().split())
a=[0,a1];b=[0]*(n+1)
for i in range(2,n+1):
    a.append((a[i-1]+7*i)%m);
for i in range(1,n+1):
    for j in range(i,n+1,i):
        b[j]+=a[i]
ans=b[1]
for i in range(2,n+1):
    ans^=b[i]
print(ans)

发表于 2026-01-14 11:37:44 回复(0)

提交观点

问题信息

难度：

2条回答 3收藏 34浏览

many sum

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题