[CQOI2015]选数
题目描述
我们知道，从区间([L,H])（(L)和(H)为整数）中选取(N)个整数，总共有((H-L+1)^N)种方案。
小(z)很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的(N)个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。
你的任务很简单，小(z)会告诉你一个整数(K)，你需要回答他最大公约数刚好为(K)的选取方案有多少个。由于方案数较大，你只需要输出其除以(1000000007)的余数即可。
输入输出格式
输入格式：
输入一行，包含(4)个空格分开的正整数，依次为(N)，(K)，(L)和(H)。
输出格式：
输出一个整数，为所求方案数。
说明
对于(100\%)的数据，(1 le N, K le 10^9)，(1 le L le H le 10^9)，(H-L le10^5)
暴力反演一波你会发现要求这个式子
[sum_{d=1}^{lfloorfrac{r}{k}
floor}mu(d)(lfloorfrac{lfloorfrac{r}{k}
floor}{d}
floor-lfloorfrac{lceilfrac{l}{k}
ceil-1}{d}
floor)
]
需要使用杜教筛，不想学，发现还有一个神仙的(DP)
令(r=lfloorfrac{r}{k} floor,l=lceilfrac{l}{k} ceil)
问题等价于问互质的方案数
引理：区间([l,r])任意两个不相等数的最大公约数的大小不会超过(r-l)
证明：取任意互质的数(a,b)，将它们同乘(m)，而(r-l)取最小值时((b-a) imes m ge m)，得证
（证明是从别处抄的，说实话不太懂QAQ）
设(dp_{i})代表以(i)为最大公约数的数量，且所选的数不全相等。
考虑(g_i)为(i)为约数的数量，同样也是所选的不全相等。
（不全相等是处于统计方便考虑）
显然
[g_i=(lfloorfrac{r}{i}
floor-lfloorfrac{l-1}{i}
floor)^n-(lfloorfrac{r}{i}
floor-lfloorfrac{l-1}{i}
floor)
]
根据容斥原理
[dp_i=g_i-sum_{i|d}^rdp_d
]
注意要特判(l=1)，因为这个时候可以全相等
Code:
#include <cstdio>
#define ll long long
const int N=1e5+10;
const ll mod=1e9+7;
ll n,k,l,r;
ll dp[N];
ll quickpow(ll d,ll k)
{
ll f=1;
while(k)
{
if(k&1) f=f*d%mod;
d=d*d%mod;
k>>=1;
}
return f;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
l=(l-1)/k+1,r=r/k;
for(ll i=1;i<=r-l;i++)
{
ll cnt=(r/i-(l-1)/i);
dp[i]=quickpow(cnt,n)-cnt;
}
for(ll i=r-l;i;i--)
for(ll j=i<<1;j<=r-l;j+=i)
(dp[i]-=dp[j])%=mod;
printf("%lld
",(dp[1]+(l==1)+mod)%mod);
return 0;
}
2018.10.20