传送门

题意：

从区间[L,H]（L和H为整数）中选取N个整数，求N个整数最大公约数刚好为K的选取方案有多少个，答案模1e9+7
1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5

Solution：

并不是非常理解莫反怎么做= =

注意到H-L≤10^5
尝试在这上面做文章
首先简化题意：
[⌈Lk⌉,⌊Hk⌋] 中可重复的选出N个数使其gcd=1
那么我们可以用f[i]表示在区间中选出的数的最大公约数为i且选出的数不全相同的方案数，我们先求出区间中i的倍数个数x，暂时令 f[i]=xN−x
但是此时的f[i]实际上是最大公约数为i及i的倍数的方案数，所以说我们需要去重：假如我们知道了f[2i],f[3i]的最终结果，那么我们就把f[i]分别减去这些数即可，这可以用倒推来实现.
有点类似容斥
P.S：为什么要不全相同呢？因为如果全部相同，那么我们得到的gcd就有可能>r-l,是会超过上界的，考虑这种情况的话就很难递推了。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,k,l,r;
const int mod=1e9+7;
int f[100010];
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&l,&r);
    l=(l+k-1)/k;r=r/k;
    for (int i=1;i<=r-l;i++)
    {
        int L=l,R=r;
        L=(L+i-1)/i;R=R/i;
        if (L>R) continue;
        f[i]=(fast_pow(R-L+1,n)-(R-L+1)+mod)%mod;
    }
    for (int i=r-l;i>=1;i--)
    {
        for (int j=2*i;j<=r-l;j+=i)
            f[i]=(f[i]-f[j]+mod)%mod;
    }
    if (l==1) f[1]++;
    printf("%d",f[1]%mod);
}