many sum【牛客tracker 每日一题】

many sum

时间限制：1秒 空间限制：512M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

定义序列A AA：
A 1 = A_1=A1​=输入的东西~~
A i = ( A i − 1 + 7 ∗ i ) A_i=(A_{i−1}+7∗i)Ai​=(Ai−1​+7∗i)%M , i ≥ 2 M,i≥2M,i≥2
定义序列B BB：B i = ∑ d ∣ i A d B_i=∑_{d∣i}A_dBi​=∑d∣i​Ad​​
你要求⊕ i = 1 N B i ⊕_{i=1}^NB_i⊕i=1N​Bi​

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

其中⊕ ⊕⊕表示异或，也就是说你需要把所有的B i B_iBi​异或起来输出

输入描述：

第一行三个整数N , A 1 , M N,A_1,MN,A1​,M

输出描述：

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

示例1

输入：

10 10 313

输出：

441

备注：

1 ≤ N ≤ 2 × 10 6 , 0 ≤ A 1 , M < 10 4 1≤N≤2×10^6,0≤A_1,M<10^41≤N≤2×106,0≤A1​,M<104
通过此题的同学，不妨来想一些如果N = 2 × 10 7 N=2×10^7N=2×107的时候该怎么做呢？（由于是小白月赛于是就删了个0 00)

解题思路

首先初始化序列A AA的首项A 1 A_1A1​为输入值，按照递推公式A i = ( A i − 1 + 7 ∗ i ) % M A_i=(A_{i-1}+7*i)\%MAi​=(Ai−1​+7∗i)%M遍历计算出1 11到n nn的所有A AA数组元素，完成O ( n ) O(n)O(n)的序列预处理；接着采用倍数枚举法求解B BB数组，B [ i ] B[i]B[i]为i ii的所有约数d dd对应的A d A_dAd​之和，遍历每个d dd作为约数，对其所有倍数j jj累加A d A_dAd​到B j B_jBj​中，该方式比枚举每个数的约数更高效，时间复杂度为O ( n l o g n ) O(n log n)O(nlogn)；最后初始化异或答案为B 1 B_1B1​，遍历2 22到n nn的所有B i B_iBi​依次做异或运算，累计得到最终结果。该方法各步骤无冗余计算，完美适配N ≤ 2 × 10 6 N≤2×10^6N≤2×106的规模，精准递推序列与统计约数和，高效求出所有B i B_iBi​的异或总和。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e6+10;ll a[N],b[N];intmain(){ll n,m;cin>>n>>a[1]>>m;for(ll i=2;i<=n;i++)a[i]=(a[i-1]+7*i)%m;for(ll i=1;i<=n;i++)for(ll j=i;j<=n;j+=i)b[j]+=a[i];ll ans=b[1];for(ll i=2;i<=n;i++)ans=ans^b[i];cout<<ans<<endl;return0;}