Description：

对所有 $i\in[1,k]$ 求出长为 $n$ 的每个数在 $[1,i]$ 的，所有数 $\gcd$ 为 $1$ 的数列个数。

$1\leqslant n,k\leqslant 2\times 10^6$

Solution：

其实让求的就是： $$ b_k=\sum_{i_1=1}^k\sum_{i_2=1}^k\cdots\sum_{i_n=1}^k[\gcd(i_1,i_2,\dots,i_n)=1] $$ 反演得： $$ b_k=\sum_{d=1}^k\mu(d)\lfloor\frac k d\rfloor^n $$ 如果只有单点询问的话显然可以除法分块优化到 $O(n\sqrt n)$ 。

但是这个要对所有的 $[1,k]$ 求，看了题解发现可以差分，也就是说 $d$ 只对所有 $k\geqslant d$ 产生贡献，而贡献每 $d$ 个一段每段不相同，那就可以差分，每次在交界处更改，时间复杂度是 $O(k\ln k)$ 的。

要预处理幂。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 2000010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int mu[MAXN];

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

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

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int diff[MAXN];

int pows[MAXN];

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 2;i <= k;++i)isprime[i] = true;

	mu[1] = 1;

	for(int i = 2;i <= k;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(int j = 1;j <= tot && i * prime[j] <= k;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else

			{

				mu[i * prime[j]] = -mu[i];

			}

		}

	}

	for(int i = 1;i <= k;++i)pows[i] = power(i,n);

	for(int i = 1;i <= k;++i)

	{

		for(int j = i;j <= k;j += i)

		{

			diff[j] = ((diff[j] + mu[i] * (pows[j / i] - pows[j / i - 1] + MOD) % MOD) % MOD + MOD) % MOD;

		}

	}

	int ans = 0;

	for(int i = 1;i <= k;++i)

	{

		diff[i] = (diff[i] + diff[i - 1]) % MOD;

		ans = (ans + (diff[i] ^ i)) % MOD;

	}

	cout << ans << endl;

	return 0;

}