——题目出处zhoutb2333
题解：
3e6可以带一个log
又是下取整问题。但是分块会TLE。
这样考虑，我们把式子拆成两个部分。
我们先算出来每一个x的[ai/x]项，再算出来[x/ai]项。之后做和。
[x/ai]:
x和ai的倍数有一些关系。
发现，假设现在x|ai，且x/ai=k, 那么，对于任意的（x~x+ai-1）[x/ai]=k;
所以，我们可以反过来，对于每一个ai，枚举ai的倍数，在ai的每个倍数的位置上++，这个桶叫val
那么，一个x，[x/ai]的值，就是val[1~x]的和！即一个前缀和。
所以我们外层循环i，给ai的倍数打标记 。
但是会被卡，ai=1时，复杂度M^2
所以给ai再开一个桶，cnt[i]表示值为i的ai有多少个。
枚举i的倍数即可，每次val+=cnt[i]，一次加了许多个。
复杂度：M*(1/1+1/2+1/3+...1/M)= MlogM
另外一部分：
[ai/x]
ai和x的倍数有一些关系。
这次就考虑外层枚举x，思路和上面差不多。
枚举x的每一个倍数j，k=j/x，
那么，对于数值在（k*x,k*x+x-1）的区间内的所有的ai，[ai/x]=k
把刚才那个桶cnt，进行一个前缀和。
所以，对于这个x，每个倍数j的贡献是：(sum(k*x+x-1)-sum(k*x-1))*k
复杂度同上。
然后两边做和就可以了。
注意：脑残的一点：n大于2e5的手动构造，mod M再加1，不是mod(M+1)
显然啊，Ai数值不能是(0,M）的，而是(1,M）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3000000+4; ll n,m; ll a[N]; ll cnt[N],tot; ll val[N]; ll lp[N]; ll s[N]; int main() { scanf("%lld%lld",&n,&m); if(n<2e5){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]); cnt[a[i]]++; } } else{int t; scanf("%lld",&a[1]); cnt[a[1]]++; for(int i=2;i<=n;i++){ a[i]=(1LL*a[i-1]*a[i-1]+1LL*7*a[i-1]+34221)%m+1; cnt[a[i]]++; } } for(int i=1;i<=m;i++){ s[i]=s[i-1]+cnt[i]; if(!cnt[i]) continue; for(int j=i;j<=m;j+=i){ val[j]+=cnt[i]; } } //for(int i=1;i<=m;i++){ /// cout<<s[i]<<endl; //} for(int i=1;i<=m;i++){ for(int j=i;j<=m;j+=i){ lp[i]+=(s[min((ll)j+i-1,m)]-s[j-1])*(j/i); } } ll ans=0; for(int i=1;i<=m;i++){ val[i]+=val[i-1]; //cout<<val[i]<<" "<<lp[i]<<endl; ans^=(lp[i]+val[i]); } printf("%lld",ans); return 0; }