出题人题解 | #算式子#

原题解链接：https://ac.nowcoder.com/discuss/149990

令$cnt[y]cnt[y]$为$a_{i}a\_i$中$yy$的出现次数。

首先对于每个$1\le x\le m1\; \backslash leq\; x\; \backslash leq\; m$ 考虑 ${\sum }_{i=1}^n\lfloor \frac{a_i}{x}\rfloor \backslash sum\_\{i=1\}^\{n\}\backslash left\backslash lfloor\backslash frac\{a\_\{i\}\}\{x\}\backslash right\backslash rfloor$, 我们发现如果 $\lfloor \frac{a_i}{x}\rfloor =k\backslash left\backslash lfloor\backslash frac\{a\_\{i\}\}\{x\}\backslash right\backslash rfloor=k$，那么，是一个区间。 所以我们可以首先枚举$xx$，再枚举$xx$的倍数$k\times xk\backslash times\; x$,然后把$\mathrm{cnt}[k\times x]\sim \mathrm{cnt}[(k+1)\times x-1]\backslash operatorname\{cnt\}[k\; \backslash times\; x]\; \backslash sim\; \backslash operatorname\{cnt\}[(k+1)\; \backslash times\; x-1]$统计进答案即可。

然后考虑$\lfloor \frac{x}{A_i}\rfloor \backslash left\backslash lfloor\backslash frac\{x\}\{A\_\{i\}\}\backslash right\backslash rfloor$。我们发现当$xx$从$k\times a_i-1k\backslash times\; a\_i-1$变为$k\times a_{i}k\; \backslash times\; a\_i$时，这个值多了$11$。所以我们可以对于每个$a_{i}a\_i$，枚举它的倍数，然后往这个倍数的位置打上$+1+1$的标记，最后前缀和即可求出每个位置的答案。

但是这样做的复杂度为${\sum }_{i=1}^n\lfloor \frac{m}{a_i}\rfloor =O(n\times m)\backslash sum\_\{i=1\}^\{n\}\backslash left\backslash lfloor\backslash frac\{m\}\{a\_\{i\}\}\backslash right\backslash rfloor=O(n\; \backslash times\; m)$（当$a_{i}a\_i$都很小时）。

改进一下,如果有多个$a_{i}a\_i$的值相同,那么这些$a_{i}a\_i$打的标记都相同。所以我们可以改为枚举每个值$1\le y\le m1\le y\le m$,枚举$yy$的倍数，然后一次就打$+cnt[y]+cnt[y]$的标记。

复杂度为${\sum }_{i=1}^m\lfloor \frac{m}{i}\rfloor =O(m\log m)\backslash sum\_\{i=1\}^\{m\}\backslash left\backslash lfloor\backslash frac\{m\}\{i\}\backslash right\backslash rfloor=O(m\; \backslash log\; m)$。

	#include<bits/stdc++.h>
	#define maxn 2000010
	#define ll long long
	using namespace std;
	
	int a[maxn],b[maxn],n,m;
	ll tag[maxn],ans=0;
	inline void read(int &x){
		char ch=x=0;
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch))
			x=x*10+ch-'0',ch=getchar();
	}
	int main(){
		read(n),read(m);
			for(int i=1;i<=n;i++)
				read(a[i]),b[a[i]]++;
		for(int i=1;i<=m;i++){
			for(int j=i;j<=m;j+=i)
				tag[j]+=b[i];
		}
		for(int i=1;i<=m;i++)
			b[i]+=b[i-1],tag[i]+=tag[i-1];
		
		for(int i=1;i<=m;i++){
			for(int j=1;j*i<=m;j++){
				int st=i*j,ed=min(m,i*(j+1)-1);
				tag[i]+=1LL*(b[ed]-b[st-1])*j;
			}
		}
		for(int i=1;i<=m;i++)
			ans^=tag[i];
		printf("%lld\n",ans);
		return 0;
	}