zcmimi's blog
查看原题

点击跳转

首先L=\left \lceil \frac LK\right \rceil,H=\left \lceil \frac HK\right \rceil

问题转化为在[L,H]中取 N\gcd=1的数 的方案数

f_i为选出 N个不完全相同\gcd=i的数 的方案数

x[L,R]i的倍数的个数,x=\sum_{j=L}^H [i|j]=\left \lfloor \frac Hi \right \rfloor-\left \lfloor \frac Li \right \rfloor

暂时令f_i=x^N-x(所有减去完全相同的)

这时候f_i实际上是选出 N个不完全相同i|\gcd的数 的方案数

假设我们已经知道了f_{2i},f_{3i},...的最终结果

那么把f_i减去f_{2i},f_{3i},...就可以了

#include<cstdio>
const int N=100011,P=1000000007;
int n,K,L,H,f[N];
inline int pw(int x,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return ans;
}
int main() {
    scanf("%d%d%d%d",&n,&K,&L,&H);
    L=L/K+(L%K!=0);
    H/=K;
    if(L>H)return puts("0"),0;
    for(int i=1;i<=H-L;++i) {
        int l=L,r=H;
        l=l/i+(l%i!=0);
        r/=i;
        if(l<=r)f[i]=(pw(r-l+1,n)-(r-l+1)+P)%P;
    }
    for(int i=H-L;i;--i)
        for(int j=i<<1;j<=H-L;j+=i)
            f[i]=(f[i]-f[j]+P)%P;
    if(L==1)(f[1]+=1)%=P;
    printf("%d\n",f[1]);
}
LG 3172 [CQOI2015]选数
comment评论
Search
search