题意
我们称一个大小为 \(n\) 的数组 \(a\) 互质，当且仅当 \(\gcd(a_1,a_2,\cdots,a_n)=1\)。
给定 \(n,k\)，对于每个 \(i\) \((1\le i\le k)\)，你都需要确定这样的数组的个数——长度为 \(n\) 的互质数组 \(a\) ，满足对每个 \(j\) \((1\le j\le n)\)，都有 \(1\le a_j\le i\)。
分析
我们设 \(f(x)\) 为 \(x\) 所对应的互质数组的个数。
按照题意，可以列出这样一个式子：
\[f(x)=\sum^x_{a_1=1}\sum^x_{a_2=1}\cdots\sum^x_{a_n=1}\left[\gcd^n_{i=1}a_i=1\right] \]简单推一下式子：
\[\begin{aligned} f(x)&=\sum^x_{a_1=1}\sum^x_{a_2=1}\cdots\sum^x_{a_n=1}\left[\gcd^n_{i=1}a_i=1\right]\\ &=\sum^x_{a_1=1}\sum^x_{a_2=1}\cdots\sum^x_{a_n=1}\varepsilon\left(\gcd^n_{i=1}a_i\right)\\ \end{aligned} \]因为 \(\mu*\mathbf{1}=\varepsilon\)，即 \(\varepsilon(x)=\sum_{d|x}\mu(d)\) 所以有：
\[\begin{aligned} f(x)&=\sum^x_{a_1=1}\sum^x_{a_2=1}\cdots\sum^x_{a_n=1}\sum_{d|\gcd^n_{i=1}a_i}\mu(d)\\ &=\sum^x_{a_1=1}\sum^x_{a_2=1}\cdots\sum^x_{a_n=1}\sum_{d|a_1,\cdots,d|a_n}\mu(d)\\ \end{aligned} \]变换求值顺序，枚举 \(d\)：
\[\begin{aligned} f(x)&=\sum^x_{d=1}\mu(d)\sum^{\lfloor\frac{x}{d}\rfloor}_{a_1=1}\sum^{\lfloor\frac{x}{d}\rfloor}_{a_2=1}\cdots\sum^{\lfloor\frac{x}{d}\rfloor}_{a_n=1}1\\ &=\sum^x_{d=1}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor^n \end{aligned} \]于是我们得到了一个 \(O(k\sqrt{k}+k\log n)\) 的做法。
在 \(n,k\leq2\times10^6\) 的规模下，无法通过本题。
有个显然的引理：
\[d|x \Leftrightarrow \left\lfloor\frac{x}{d}\right\rfloor = \left\lfloor\frac{x-1}{d}\right\rfloor+1 \]据此考虑差分：
\[\begin{aligned} \Delta f(x)&=f(x)-f(x-1)\\ &=\sum^x_{d=1}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor^n-\sum^{x-1}_{d=1}\mu(d)\left\lfloor\frac{x-1}{d}\right\rfloor^n\\ &=\sum^x_{d=1}\mu(d)\left(\left\lfloor\frac{x}{d}\right\rfloor^n-\left\lfloor\frac{x-1}{d}\right\rfloor^n\right)\\ \end{aligned} \]根据上述引理，当且仅当 \(d|x\) 时 \(\left(\left\lfloor\frac{x}{d}\right\rfloor^n-\left\lfloor\frac{x-1}{d}\right\rfloor^n\right) \neq 0\)，所以上式可以如下改写：
\[\begin{aligned} \Delta f(x)&=\sum_{d|x}\mu(d)\left(\left\lfloor\frac{x}{d}\right\rfloor^n-\left\lfloor\frac{x-1}{d}\right\rfloor^n\right)\\ \end{aligned} \]所以，我们可以枚举 \(d\)，然后将所有满足 \(d|x\) 的 \(\Delta f(x)\) 加上 \(\mu(d)\left(\left\lfloor\frac{x}{d}\right\rfloor^n-\left\lfloor\frac{x-1}{d}\right\rfloor^n\right)\)。
通过前缀和统计答案。
时间复杂度 \(O(k\log n+k \log k)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000006
#define mod 1000000007
int mu[maxn];
bool vis[maxn];
vector<int> pri;
void init()
{
mu[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) mu[i]=-1, vis[i]=1, pri.emplace_back(i);
for(auto p:pri)
{
if(p*i>=maxn) break;
vis[p*i]=1;
if(i%p==0) break;
mu[i*p]=-mu[i];
}
}
}
int ksm(int64_t x, int l)
{
int64_t ret=1;
for(;l;l>>=1, x=x*x%mod)
if(l&1) ret=ret*x%mod;
return ret;
}
int lev[maxn], det[maxn];
int main()
{
int n, k;
cin>>n>>k;
init();
for(int i=1;i<=k;i++)
lev[i]=ksm(i, n);
for(int d=1;d<=k;d++)
for(int j=1;d*j<=k;j++)
det[d*j]=((det[d*j]+mu[d]*(mod+(lev[j]-lev[j-1])%mod)%mod)%mod+mod)%mod;
int ans=0, otp=0;
for(int i=1;i<=k;i++)
otp=(otp+(i^(ans=(ans+det[i])%mod)))%mod;
cout<<otp%mod;
}