题解：「WWOI R1」WsW 的笔

这里是出题人题解。

思路

为了方便表达，令 $n=b-a+1$。
如果编号为 $i$ 的笔送给谁已经确定，那么编号为 $i\times k^t,t\in \mathbb{N}$ 的笔送给谁就都确定了。我们把这些互相依赖的笔分为一组，如果一组中某一支笔送给谁确定了，一组中所有的笔送给谁就都确定了。
组和组之间互不影响，假设分出了 $m$ 组，答案就是 $2^m$。
如何求出有多少组呢？可以用每一组中最小的编号来指代这一组。可以发现，满足 $i\bmod k\ne0$ 或 $i<a\times k$ 的编号 $i$ 一定是某一组中最小的编号；这两个条件都不满足的编号 $i$，一定不是某一组中最小的编号。

所以只需要求出满足这两个条件的 $i$ 的数量，再容斥去掉重复的即可。

对于特殊性质 A，上面的容斥会出错，需要特判。

特判时如果直接 $a\times k>b$ 会爆 unsigned long long，要把式子转化成 $a>b/k$。

最后用快速幂计算方案数。

时间复杂度为 $O(T\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull mod=1e9+7;
ull p(ull x){
    ull ans=1,t=2;
    while(x){
        if(x&1)(ans*=t)%=mod;
        (t*=t)%=mod;
        x>>=1;
    }
    return ans;
}
ull g(ull l,ull r,ull k){
	return (r-r/k)-(l-l/k);
}
void work(){
	ull k,a,b; cin>>k>>a>>b;
	if(b/k<a)cout<<p(b-a+1)<<'\n';
	else cout<<p(g(a,b,k)-g(a,a*k-1,k)+a*(k-1))<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--)work();
	return 0;
}