首页 > 试题广场 >

many sum

[编程题]many sum

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

算法知识视频讲解

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)