闲言
赛时ABD，C题没做出，赛时其实想到过前缀和，然后就是没太想清楚怎么高效的利用前缀信息。
Problem - C - Codeforces
容易发现，当一个数是另一个数的平方时，有奇数个因数。
而区间得到的结果，最多是2*n-1，联系数据范围，对答案有贡献（减少）的数较少。
所以，利用异或运算的可逆性，从对答案有贡献的值倒推。
而为了实现区间的倒推，可以尝试记录下前缀和s的当前值，每个前缀和出现过的次数（其实也就是s[p-1]出现的次数， p为让[p, i] 的区间异或和符合题目的区间起点）
代码语言：javascript复制void solve() {
LL n;
cin >> n;
vector<int> cnt(2*n);
int s = 0;
LL sum = 0;
cnt[s] ;
for(int i = 0; i < n; i ) {
int x;
cin >> x;
s ^= x;
for(LL j = 0; j*j < 2*n; j ) {
LL t = ((j*j)^s);
if(t < 2*n)
sum = cnt[t];
}
cnt[s] ;
}
cout << n*(n 1)/2-sum << 'n';
}Problem - E - Codeforces
因为发现题目中的总花费肯定是选的组数 边的条数，那么就让选的组数尽可能小，就需要选的组尽可能大，所以考虑从大往小贪心枚举，严谨证明我这里可能给不太出（（
然后，思考如何高效找出gcd = k的组合。
由于点的编号是1~n连续的（是不是[L, R]连续区间也是这样做挺好？），找出k的倍数的个数，理论上组数就是{n/k choose 2}，但是由于是k倍数的组合有可能gcd = tk spacespacespace (t in Z bigcap space t geq 2)，所以，令a[x]为gcd=x的组合的数量，
void solve() {
LL n, m;
cin >> n >> m;
vector<LL> a(n); // can't use a[n]
LL res = 0;
for(LL i = n-1; i >= 2; i --) { // i -> gcd & cost
LL k = i-1; // edge can choose in one group
a[i] = (n/i)*(n/i-1)/2;
for(LL j = i*2; j < n; j = i)
a[i] -= a[j];
LL edges = a[i]/k*k;
if(edges > m)
edges = m/k*k;
m -= edges;
res = edges/k*i;
}
if(m > 0) res = -1;
cout << res << 'n';
}
