题意:but

有 $T$ 组询问。每组询问给定 $a,b,k,l,r$，求

$$\sum\limits_{i=l}^{r}\left\lfloor\frac{\gcd(i,(i+1)^k+a)}{b}\right\rfloor$$

答案对 $10^9-1$ 取模。

思考路径：

First

首先，对 $(i+1)^k$ 做二项式展开，然后辗转相除

得到原式化为：
$\sum\limits_{i=l}^{r}\left\lfloor\frac{\gcd(i,1+a)}{b}\right\rfloor$

Second

直接枚举 $i$ 显然不可行，考虑去枚举 $gcd$ ，然后去计算每个 $gcd$ 造成了多少贡献

问题转化为求 $i\in[l,r]$ 且 $\gcd(i,x)=y$ 的个数

Last

经典问题，倒着容斥一遍即可

这一部分具体见代码注释

$over$

$Code:$

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9-1,N=15;

int a,b,k,l,r,T,pr[N],n,t,p[1<<N],cnt,s[1<<N];

int ans,res;

inline int md(int x){
    return x<mod?x:x-mod;
} 

inline int lb(int x){
    return x&-x;//lb辅助线性递推
}

inline int get(int x,int y){//在1~x里找与y互质的数
    //注意这里，由于y是枚举的a/公因数,所它的质因数必定是a的质因数 
    cnt=0;res=0;
    for(int i=1;i<=n;i++) {
        //由于容斥，可以考虑适当卡常 
        if(y%pr[i]==0){
            p[1<<cnt]=pr[i];cnt++;
        }
    }
    for(int i=1;i<(1<<cnt);i++) p[i]=p[lb(i)]*p[i^lb(i)];//线性递推算出各种情况,如果i的j位为1，表示pr[j]被选了
//  printf("over");
    for(int i=0;i<(1<<cnt);i++) res+=x/p[i]*(s[i]&1?-1:1);
    //x/p[i]-->1~x里有多少个是p[i]的倍数
    //后面的是容斥系数，先-一个质因数的，再+两个减重的……
    return res;
}

int main(){
//  freopen("but.in","r",stdin);
//  freopen("but.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<(1<<N);i++) {
        s[i]=s[i^lb(i)]+1;//精妙的线性递推，算出容斥系数（二进制里1的个数）
    }
    p[0]=1;//容斥准备，应当设为1 
    while(T--){
        scanf("%d%d%d%d%d",&a,&b,&k,&l,&r);
        //gcd()
        a++;t=a;
        n=0;//多测要清空！！
        for(int i=2;i<=t/i;i++){
            if(t%i==0){
                pr[++n]=i;
                while(t%i==0) t/=i;//找出它的所有质因数
            }
        }
        if(t!=1) pr[++n]=t;//注意这里是t！=1，不是t!=0
        for(int i=1,t;i<=a/i;i++){
            if(a%i==0){
                /*
                复杂度分析：枚举因数O(d)*至多九个质因数的容斥O(2^9)
                */
                t=i;
                ans=md(ans+1ll*t/b*(get(r/t,a/t)-get((l-1)/t,a/t))%mod);
                if(i*i!=a) {
                    t=a/i;
                    ans=md(ans+1ll*t/b*(get(r/t,a/t)-get((l-1)/t,a/t))%mod);
                    //小心这里，转换因数想不过来可以开个零食变量存存 
                }
            }
        }
        printf("%d\n",ans);
        ans=0;
    }
    return 0;
}