Pascal(fpc 3.0.2) 解法, 执行用时: 796ms, 内存消耗: 31584K, 提交时间: 2018-10-19 19:46:47

var
  a,b:array[0..2000001]of int64;
  n,m,i,j,x:longint;
  ans:int64;
begin
  read(n,m);
  for i:=1 to n do
  begin
    read(x);
    inc(a[x]);
  end;
  for i:=1 to m do
  begin
    j:=i;
    while j<=m do
    begin
      inc(b[j],a[i]);
      inc(j,i);
    end;
  end;
  for i:=1 to m do
    inc(b[i],b[i-1]);
  for i:=m downto 1 do
    inc(a[i],a[i+1]);
  for i:=1 to m do
  begin
    j:=i;
    while j<=m do
    begin
      inc(b[i],a[j]);
      inc(j,i);
    end;
  end;
  for i:=1 to m do
    ans:=ans xor b[i];
  writeln(ans);
end.

C++14(g++5.4) 解法, 执行用时: 556ms, 内存消耗: 31716K, 提交时间: 2020-07-14 19:27:24

#include<bits/stdc++.h>
#define int long long
#define N 5000005
using namespace std;
int sum[N],b[N],n,m,x,ans;
signed main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) scanf("%d",&x),b[x]++;
    for (int i=1;i<=m;i++)
        for (int j=i;j<=m;j+=i) sum[j]+=b[i];
    for (int i=1;i<=m;i++) sum[i]+=sum[i-1];
    for (int i=m;i;i--) b[i]+=b[i+1];
    for (int i=1;i<=m;i++)
        for (int j=i;j<=m;j+=i) sum[i]+=b[j];
    for (int i=1;i<=m;i++) ans^=sum[i];
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 680ms, 内存消耗: 31680K, 提交时间: 2020-07-14 21:42:45

#include<bits/stdc++.h>
using namespace std;
const int M=2e6+5;
long long n,m,x,ans,cnt[M],sum[M];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&x),cnt[x]++;
	for(int i=1;i<=m;i++)for(int j=i;j<=m;j+=i)sum[j]+=cnt[i];
	for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
	for(int i=m;i>=1;i--)cnt[i]+=cnt[i+1];
	for(int i=1;i<=n;i++)for(int j=i;j<=m;j+=i)sum[i]+=cnt[j];
	for(int i=1;i<=m;i++)ans^=sum[i];
	printf("%lld\n",ans);
	return (0-0);
}