首页 > 试题广场 >

many sum

[编程题]many sum

热度指数：971 时间限制：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)

算法知识视频讲解

kilomatutinal

发表于 2026-01-14 01:40:47

题解前先科普一下喵！序列 B 的定义基于数论中的约数和：对于每个i，B[i] = ∑ A[d]，其中d是i的所有正约数（即d能整除i）。举个栗子喵！B[4]=A[1]+A[2]+A[4]这下就能看懂了吧正式讲解代码了喵！A[1]直接赋值为输入的a1。不过这里有个小细节喵：按照题目严格来说，A[1]应展开全文

BaiJay

发表于 2026-01-14 10:17:06

当你发现要优化一下时间复杂度就可以暴力过be like #include <bits/stdc++.h> #define int long long using namespace std; #define endl '\n' #define pb push_back #define u 展开全文

软件25_4刘卓生

发表于 2026-01-15 23:18:08

题干并不清晰，所以这里重述一下：给定三个整数 , , ，定义两个序列如下：序列：序列：请你计算：其中表示按位异或（XOR）。核心思路核心观察 1. 不取模！题目明确说 “ 输入的东西”，因此：即使，也不能写成 A[1] = a % m 只有时才展开全文

_changbin

发表于 2026-01-14 11:40:25

倍数分配法思路(Onlogn):我们按 j 枚举 1~n，把 a[j] 加到所有 j 的倍数上：j = 1 → i=1,2,3,4,5,6 加 a[1]=10j = 2 → i=2,4,6 加 a[2]=24j = 3 → i=3,6 加 a[3]=45j = 展开全文

牛客511341922号

发表于 2026-01-14 17:08:19

首先，数组 A 的递推是线性的，可以直接递推出来。然后考虑数组 B，直接枚举 i 的约数不容易，但是枚举 i 的倍数却很简单，所以我们考虑处理每个 A[i] 带给 B[j] () 的贡献。从 1 到 n 枚举 i从 i 到 n 枚举 j，每次递进 i。B[j] += A[i]处理完后，直接求答案即可展开全文

此在Dasein

发表于 2026-01-14 00:58:20

1. 问题分析本题的核心要求是处理两个具有依赖关系的序列和。序列 A：基于线性同余的递推关系，仅依赖于。这是一个单调生成的序列。序列 B：定义为的所有约数对应的之和。这是一个经典的数论变换问题（Dirichlet Convolution 的变种，即，其中是全 1 展开全文

TimothyStarman

发表于 2026-01-14 09:33:15

埃氏筛法根据题意序列表示是的所有因子项的和，即对于每一个数如果简单判断因子，其复杂度会达到导致超时。那么我们考虑使用筛法：对于每一个下标（），以及所有满足的整数，我们将的值累加到上。这样，总的操作次数约为。由于调和级数的性质，（其中为欧拉常数，当时）展开全文

YunBaichuan

发表于 2026-01-14 10:38:57

思路：整体来说就是构造出A、B数组，然后把B数组的元素异或起来。对于构造A数组来说，直接根据题意模拟即可；对于构建B数组来说，首先要注意d | i表示d去整除i，而不是i去整除d，这里我开始就弄错了，然后就可以用埃式筛来构建B数组了。简单来说，埃式筛就是两层for循环，外层i的步长为1，内层j的步长展开全文