【洛谷P3172】选数

题目

题目链接：https://www.luogu.com.cn/problem/P3172
我们知道，从区间 ([L,H])（(L) 和 (H) 为整数）中选取 (N) 个整数，总共有 ((H-L+1)^N) 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 (N) 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 (K)，你需要回答他最大公约数刚好为 (K) 的选取方案有多少个。
由于方案数较大，你只需要输出其除以 (10^9+7) 的余数即可。
(n,k,L,Hleq 10^9,H-Lleq 10^5)。

思路

令 (R=H)。
直接莫比乌斯反演显然有

[ans=sum_{d|i}mu(frac{i}{d})left(lfloorfrac{R}{i} floor-lfloorfrac{L-1}{i} floor ight)^n ]

换个枚举方式

[ans=sum^{lfloorfrac{R}{d} floor}_{i}mu(i)left(lfloorfrac{R}{i·d} floor-lfloorfrac{L-1}{i·d} floor ight)^n ]

后面那个玩意可以整除分块，然后我们只需要快速计算 (mu) 的前缀和。杜教筛即可。

代码

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

const int N=5000010,MOD=1e9+7;
int m,n,L,R,d,prm[N],mu[N];
ll ans;
bool v[N];
map<int,int> sum;

void findprm(int n)
{
	mu[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!v[i]) prm[++m]=i,mu[i]=-1;
		for (int j=1;j<=m;j++)
		{
			if (i>n/prm[j]) break;
			v[i*prm[j]]=1; mu[i*prm[j]]=-mu[i];
			if (i%prm[j]==0)
			{
				mu[i*prm[j]]=0;
				break;
			}
		}
	}
}

ll fpow(ll x,ll k)
{
	ll ans=1;
	x%=MOD;
	for (;k;k>>=1,x=x*x%MOD)
		if (k&1) ans=ans*x%MOD;
	return ans;
}

ll summu(int n)
{
	if (n<N) return mu[n];
	if (sum[n]) return sum[n];
	ll res=1;
	for (int l=2,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=(res-summu(n/l)*(r-l+1))%MOD;
	}
	return sum[n]=res;
}

int main()
{
	findprm(N-1);
	for (int i=1;i<N;i++) mu[i]+=mu[i-1];
	scanf("%d%d%d%d",&n,&d,&L,&R);
	L--;
	for (int l=1,r;l<=R/d;l=r+1)
	{
		int i=l*d;
		if (!(L/i)) r=R/(R/i)/d;
			else r=min(L/(L/i),R/(R/i))/d;
		ans=(ans+(summu(r)-summu(l-1))*fpow(R/i-L/i,n))%MOD;
	}
	printf("%lld",(ans%MOD+MOD)%MOD);
	return 0;
}