题解 | many sum

倍数分配法思路(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

代码如下（py）：

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)