题目
题目描述
我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。
输入输出格式
输入格式：
输入一行，包含4个空格分开的正整数，依次为N，K，L和H。
输出格式：
输出一个整数，为所求方案数。
输入输出样例
输入样例#1：
2 2 2 4
输出样例#1：
3
说明
样例解释
所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)
其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2)
对于100%的数据，1<=N,K<=10^9，1<=L<=H<=10^9，H-L<=10^5
题解
设$f(i)$表示$\gcd(a_1,a_2,…,a_{n-1},a_n)=i$的方案数
设$F(x)=\sum_{x\vert d}f(d)$，这样$F(x)$就表示$x\vert \gcd(a_1,a_2,…,a_{n-1},a_n)$的方案数
即$F(x)=(\left\lfloor\frac{H}{x}\right\rfloor-\left\lfloor\frac{L-1}{x}\right\rfloor)^n$
所以$f(x)=\sum_{x\vert d}\mu(\frac{d}{x})F(x)$
可以缩小范围到$[\left\lfloor\frac{L}{K}\right\rfloor,\left\lfloor\frac{H}{K}\right\rfloor]$，这样答案就是$f(1)$
$f(1)=\sum_{i=1}^{\left\lfloor\frac{H}{K}\right\rfloor}\mu(i)F(i)=\sum_{i=1}^{\left\lfloor\frac{H}{K}\right\rfloor}\mu(i)(\left\lfloor\frac{H}{i}\right\rfloor-\left\lfloor\frac{L-1}{i}\right\rfloor)^n$
后面那个东西可以整除分块分小于等于$L-1$和大于$L-1$讨论，既然$H$的范围是$10^9$，所以用杜教筛处理$\mu$函数
注意因为要求的不是一个特定的$\mu$的前缀和，所以不能只记录$\frac{n}{i}$的值，要用map存
代码
# include<iostream>
# include<cstring>
# include<map>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e7+5,N=205,mod=1e9+7;
int n,K,L,R,tot,ans;
int pm[MAX],u[MAX];
bool use[MAX],vis[N];
map<int,int> mu;
void dfs(int x)
{
if(x<MAX) return;
if(mu.find(x)!=mu.end()) return;
int ans=1;
for(int l=2,r,N;l<=x;l=r+1)
N=x/l,r=x/N,dfs(N),ans-=(r-l+1)*(N<MAX?u[N]:mu[N]);
mu[x]=(ans+mod)%mod;
}
void ss(int n)
{
u[1]=1;
for(int i=2;i<=n;++i)
{
if(!use[i]) pm[++tot]=i,u[i]=-1;
for(int j=1;j<=tot&&pm[j]*i<=n;++j)
{
use[pm[j]*i]=1;
if(i%pm[j]==0) break;
u[pm[j]*i]=-u[i];
}
u[i]+=u[i-1];
}
}
int Pow(int a,int b)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*ans*a%mod;
return ans;
}
int GET_MU(int x) {return x<MAX?u[x]:mu[x];}
int main()
{
scanf("%d%d%d%d",&n,&K,&L,&R),ss(min(R/=K,MAX-1)),L=(L-1)/K;
for(int l=1,r,N,M;l<=R;l=r+1)
{
N=R/l,r=R/N,M=0;
if(l<=L) M=L/l,r=min(r,L/M);
dfs(r),dfs(l-1),ans+=1ll*(GET_MU(r)-GET_MU(l-1)+mod)%mod*Pow(N-M,n)%mod;
if(ans>=mod) ans-=mod;
}
return printf("%d",ans),0;
}
