【bzoj3930】[CQOI2015]选数 莫比乌斯反演+杜教筛

题目描述

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

输入

输入一行，包含4个空格分开的正整数，依次为N，K，L和H。

输出

输出一个整数，为所求方案数。

样例输入

2 2 2 4

样例输出

3

---

题解

莫比乌斯反演+杜教筛

其中xi表示第i个数的取值。

然后这里就可以分块来求。

由于h的范围过大，所以需要使用杜教筛求mu的前缀和，详见 bzoj3944

#include <cstdio>

#include <map>

#define N 1000010

#define mod 1000000007

using namespace std;

typedef long long ll;

const int m = 1000000;

map<int , int> f;

map<int , int>::iterator it;

int mu[N] , sum[N] , prime[N] , tot;

bool np[N];

ll pow(ll x , int y)

{

	ll ans = 1;

	while(y)

	{

		if(y & 1) ans = ans * x % mod;

		x = x * x % mod , y >>= 1;

	}

	return ans;

}

int query(int n)

{

	if(n <= m) return sum[n];

	it = f.find(n);

	if(it != f.end()) return it->second;

	int i , last , ans = 1;

	for(i = 2 ; i <= n ; i = last + 1) last = n / (n / i) , ans -= (last - i + 1) * query(n / i);

	return f[n] = ans;

}

int main()

{

	int i , j , p , k , l , r , last;

	ll ans = 0;

	mu[1] = sum[1] = 1;

	for(i = 2 ; i <= m ; i ++ )

	{

		if(!np[i]) mu[i] = -1 , prime[++tot] = i;

		for(j = 1 ; j <= tot && i * prime[j] <= m ; j ++ )

		{

			np[i * prime[j]] = 1;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else mu[i * prime[j]] = -mu[i];

		}

		sum[i] = sum[i - 1] + mu[i];

	}

	scanf("%d%d%d%d" , &p , &k , &l , &r) , r /= k , l = (l - 1) / k;

	for(i = 1 ; i <= r ; i = last + 1)

	{

		last = r / (r / i);

		if(l >= i) last = min(last , l / (l / i));

		ans = (ans + (query(last) - query(i - 1) + mod) % mod * pow((ll)r / i - l / i , p) % mod) % mod;

	}

	printf("%lld\n" , ans);

	return 0;

}