CF915G Coprime Arrays

题解

（看了好半天终于看懂了）

我们先对于每一个i想，那么

我们设

我们用莫比乌斯反演

有了这个式子，可比可以求出△ans呢？我们注意到，由于那个(i/d)是下取整了的，所以i++后（下文的 i 是+1后的 i），只有当(d+1)|i 时答案有变化，于是

我们可以预处理a^n，以及用埃氏筛预处理△ans[i]

ＣＯＤＥ

#include<cstdio>

#include<cstring>

#include<vector>

#include<stack>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#include<iostream>

#define MAXN 2000005

#define LL long long

#define rg register

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

#pragma GCC optimize(2)

//#pragma G++ optimize(3)

//#define int LL

using namespace std;

inline int read() {

	int f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 - '0' + s;s = getchar();}

	return x * f;

}

LL zxy = 1e9 + 7;

LL n,m,i,j,k,s,o;

int p[MAXN],cnt;

int mu[MAXN];

LL po[MAXN],Delta[MAXN];

bool f[MAXN];

inline LL qkpow(LL a,LL b) {

	LL res = 1;

	while(b) {

		if(b & 1) res = res * a % zxy;

		b >>= 1;

		a = a * a % zxy;

	}

	return res % zxy;

}

inline void sieve(int n) {

	mu[1] = 1;

	for(int i = 2;i <= n;i ++) {

		if(!f[i]) {

			p[++ cnt] = i;

			mu[i] = -1;

		}

		for(int j = 1;j <= cnt && i * p[j] <= n;j ++) {

			int y = i * p[j];

			f[y] = 1;

			if(i % p[j] == 0) {

				mu[y] = 0;

				break;

			}

			mu[y] = -mu[i];

		}

	}

	return ;

}

signed main() {

	sieve(2000000);

	n = read();m = read();

	for(int i = 0;i <= 2000000;i ++) po[i] = qkpow(i,n);

	for(int i = 1;i <= m;i ++) {

		for(int j = i;j <= m;j += i) {

			Delta[j] = (Delta[j] + zxy +  mu[i] * 1ll * (po[j/i] - po[j/i - 1]) % zxy) % zxy;

		}

	}

	LL ans = 0,as = 0;

	for(int i = 1;i <= m;i ++) {

		as = (as + Delta[i]) % zxy;

		ans = (ans + (as ^ i)) % zxy;

	}

	printf("%lld\n",ans);

    return 0;

}

CF915G Coprime Arrays （莫比乌斯反演）的相关教程结束。