牛客练习赛29—F算式子
题目链接:传送门
题解:
代码:
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long llt;
const int N = 2000010;
const int INF = 0x3fffffff;
llt cnt1[N],cnt2[N];
int main()
{
int n,m,a;
cin >> n >> m;
for(int i = 0; i < n; ++i){
cin >> a;
cnt1[a]++;
}
for(int i = 1; i <= m; ++i){
if(cnt1[i] == 0) continue;
for(int j = i; j <= m; j += i){
cnt2[j] += cnt1[i];
}
}
for(int i = 1; i <= m; ++i)
cnt2[i] += cnt2[i-1];
for(int i = 1; i <= m; ++i)
cnt1[i] += cnt1[i-1];
llt val,ans = 0;
for(int i = 1; i <= m; ++i){
val = 0;
for(int j = i; j <= m; j += i){
int t = min(j+i-1, m);
val += (cnt1[t]-cnt1[j-1])*(j/i);
}
//cout << val << endl;
ans ^= val+cnt2[i];
}
cout << ans << endl;
return 0;
}