牛客练习赛29----F 算式子
链接：https://ac.nowcoder.com/acm/contest/6290/E
示例 (1)
输入
2 2
1 2
输出
0
示例 (2)
输入
10 10
1 3 5 5 2 5 9 3 1 10
输出
60
题解
分析公式，公式分为三种情况，当 (x=a_i) 时，结果为 (2)，其它两种情况结果加法等式中必有一个为 (0)。
当 (x≤a_i) 时，枚举每一个 (a_i/x) 结果，将整个区间进行数相加，并乘以 (a_i/x) 结果。
当 (x≥a_i) 时，枚举每一个 (a_i)，并分析它的倍数，在整个区间进行差分，最后求前缀和。
注意
- 使用筛可以降低时间复杂度
- 整除分块也可以使用筛进行求解，只有面对很多次使用才可以
代码
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 2e6+55;
ll a[maxn];
ll x[maxn],ans=0;
inline int min(int a,int b){return a<b?a:b;}
int main(){
int n,m,c;
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i){
scanf("%d",&c);++a[c];
}
for(int i=1;i<=m;++i){
if(!a[i])continue;
for(int j=i;j<=m;j+=i){
x[j]+=a[i];
}
}
for(int i=1;i<=m;++i)a[i]+=a[i-1],x[i]+=x[i-1];
for(int i=1;i<=m;++i){
for(int j=1,r;j<=m/i;++j){
r=min(m,(j+1)*i-1);
x[i]+=(a[r]-a[j*i-1])*j;
}
ans^=x[i];
}
printf("%lld
",ans);
return 0;
}