Codeforces 915 G Coprime Arrays

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Discipntion

Let's call an array a of size n coprime iff gcd(a₁, a₂, ..., a_n) = 1, where gcd is the greatest common divisor of the arguments.

You are given two numbers n and k. For each i (1 ≤ i ≤ k) you have to determine the number of coprime arrays a of size n such that for every j (1 ≤ j ≤ n) 1 ≤ a_j ≤ i. Since the answers can be very large, you have to calculate them modulo 10⁹ + 7.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 2·10⁶) — the size of the desired arrays and the maximum upper bound on elements, respectively.

Output

Since printing 2·10⁶ numbers may take a lot of time, you have to output the answer in such a way:

Let b_i be the number of coprime arrays with elements in range [1, i], taken modulo 10⁹ + 7. You have to print , taken modulo 10⁹ + 7. Here denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

Example

Input

3 4

Output

Input

2000000 8

Output

339310063

Note

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range [1, i]:

For i = 1, the only array is coprime. b₁ = 1.

For i = 2, array [2, 2, 2] is not coprime. b₂ = 7.

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. b₃ = 25.

For i = 4, arrays [2, 2, 2], [3, 3, 3], [2, 2, 4], [2, 4, 2], [2, 4, 4], [4, 2, 2], [4, 2, 4], [4, 4, 2] and [4, 4, 4] are not coprime. b₄ = 55.

一开始没有想到题目求b的整体性，，，直接用了一个简单的容斥，，，然后就T了。。

如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define ha 1000000007
#define maxn 2000005
using namespace std;
int ans[maxn],n,k,tot;inline int ksm(int x,int y){
int an=1;
for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
return an;
}inline void get(int x){
ans[x]=-ksm(x,n);
for(int i=2,j,now;i<=x;i=j+1){
now=x/i,j=x/now;
ans[x]=((ll)ans[x]+(ll)(j-i+1)*(ll)ans[now])%ha;
}ans[x]=-ans[x];
if(ans[x]<0) ans[x]+=ha;
}int main(){
scanf("%d%d",&n,&k);
ans[1]=1;
for(int i=2;i<=k;i++) get(i);tot=0;
for(int i=1;i<=k;i++){
tot+=ans[i]^i;
while(tot>=ha) tot-=ha;
}printf("%d\n",tot);
return 0;
}

后来发现还是要上反演才能过啊hhhh。

当我们求b[t]的时候：

设g(x)为gcd是x的倍数的数组个数，
显然g(x)=(t/x)^n;
设f(x)为gcd==x的数组个数，
显然g(x)=Σf(x*i)
所以=> f(x)=Σg(x*i)*μ(i)

我们求的显然是f(1),
所以b[t]=Σg(i)*μ(i)=Σ μ(i) * (t/i)^n

我们考虑通过b[t-1]推b[t]，发现只有i是t的约数时(t/i)变化了，且都是+1；而对于其他的i，(t/i)不变。

所以我们可以先预处理出b[]的差分(可以做到调和级数的N ln N，通过枚举i，但前提是你得先预处理出(1-k)的n次方最好再把次方的差分也一起算出来)。

最后求差分的前缀和就是b[]了。

正解如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define ha 1000000007
#define maxn 2000005
using namespace std;
int ans[maxn],n,k,tot;
int ci[maxn],u[maxn];
int zs[1000000],t=0;
bool v[maxn];inline void init(){
u[1]=1;
for(int i=2;i<=2000000;i++){
if(!v[i]) zs[++t]=i,u[i]=-1;
for(int j=1,w;j<=t&&(w=zs[j]*i)<=2000000;j++){
v[w]=1;
if(!(i%zs[j])) break;
u[w]=-u[i];
}
}
}inline int ksm(int x,int y){
int an=1;
for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
return an;
}int main(){
init();scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++) ci[i]=ksm(i,n);
for(int i=k;i;i--){
ci[i]-=ci[i-1];
if(ci[i]<0) ci[i]+=ha;
}for(int i=1;i<=k;i++)
for(int j=i;j<=k;j+=i){
ans[j]+=u[i]*ci[j/i];
if(ans[j]<0) ans[j]+=ha;
else if(ans[j]>=ha) ans[j]-=ha;
}for(int i=1;i<=k;i++){
ans[i]+=ans[i-1];
if(ans[i]>=ha) ans[i]-=ha;tot+=ans[i]^i;
while(tot>=ha) tot-=ha;
}printf("%d\n",tot);
return 0;
}