[CQOI2015]选数

题目链接：Click here

Solution:

先把式子列出来

\[\sum_{i_1=L} ^{H}\sum_{i_2=L}^H \dots\sum_{i_n=L}^H [gcd(i_{j=1}^n)=k]\\ \]

接下来就是莫反套路了

\[\sum_{i_1=\lfloor{L-1 \over k}\rfloor} ^{\lfloor{H\over k}\rfloor}\sum_{i_2=\lfloor{L-1 \over k}\rfloor}^{\lfloor{H\over k}\rfloor} \dots\sum_{i_n=\lfloor{L-1 \over k}\rfloor}^{\lfloor{H\over k}\rfloor} [gcd(i_{j=1}^n)=1]\\ \sum_{d=1}^{\lfloor{H\over k}\rfloor}\mu(d)\sum_{i_1=\lfloor{L-1 \over kd}\rfloor} ^{\lfloor{H\over kd}\rfloor}\sum_{i_2=\lfloor{L-1 \over kd}\rfloor}^{\lfloor{H\over kd}\rfloor} \dots\sum_{i_n=\lfloor{L-1 \over kd}\rfloor}^{\lfloor{H\over kd}\rfloor} \\ \]

把后面的东西提出来，等于\((\lfloor{H\over kd}\rfloor-\lfloor{L-1 \over kd}\rfloor)^n\)，即

\[\sum_{d=1}^{\lfloor{H\over k}\rfloor}\mu(d)(\lfloor{H\over kd}\rfloor-\lfloor{L-1 \over kd}\rfloor)^n \]

杜教筛筛\(\mu\)是基本操作，在数论分块即可

Code:

#include
#define int long long
using namespace std;
const int N=2e6+11;
const int mod=1e9+7;
const int inf=1919191919;
bool vis[N];
int L,R,n,k,cnt;
int ans,p[N],u[N];
unordered_map vu;
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int qpow(int a,int b){
    int re=1;
    while(b){
        if(b&1) re=re*a%mod;
        b>>=1;a=a*a%mod;
    }return re%mod;
}
void prepare(){
    u[1]=1;
    for(int i=2;i