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∣iAd
你要求⊕ i = 1 N B i ⊕_{i=1}^NB_i⊕i=1NBi
这样我们只要输入三个数，输出一个数啦~
其中⊕ ⊕⊕表示异或，也就是说你需要把所有的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;}