CQOI 2015 选数

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

2 2 2 4

输出 #1

3

分析

有两种做法，第一种是反演后杜教筛，第二种是容斥。
首先化简式子：
$\sum _{a_1=L}^H\sum _{a_2=L}^H...\sum _{a_n=L}^H[\gcd (a_1,a_2,....,a_n)==k]=\sum _{a_1=\lceil \frac{L}{K}\rceil }^{\lfloor \frac{H}{K}\rfloor }\sum _{a_2=\lceil \frac{L}{K}\rceil }^{\lfloor \frac{H}{K}\rfloor }...\sum _{a_n=\lceil \frac{L}{K}\rceil }^{\lfloor \frac{H}{K}\rfloor }[\gcd (a_1,a_2,....,a_n)==1]$a1​=L∑H​a2​=L∑H​...an​=L∑H​[gcd(a1​,a2​,....,an​)==k]=a1​=⌈KL​⌉∑⌊KH​⌋​a2​=⌈KL​⌉∑⌊KH​⌋​...an​=⌈KL​⌉∑⌊KH​⌋​[gcd(a1​,a2​,....,an​)==1]

第一种做法

然后我们不妨令 $L=\lceil \frac{L}{K}\rceil$L=⌈KL​⌉， $H=\lfloor \frac{H}{K}\rfloor$H=⌊KH​⌋。
然后 $原式=\sum _{x=1}^H\mu \left(x\right)(\lfloor \frac{H}{x}\rfloor -\lfloor \frac{L-1}{x}\rfloor {)}^N$原式=x=1∑H​μ(x)(⌊xH​⌋−⌊xL−1​⌋)N
然后 分块 + 杜教筛 就完事了。
复杂度 $O\left(n^{\frac{2}{3}}\right)$O(n32​)

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 3000007
#define inf 2147483647
using namespace std;
const int mod = 1e9 + 7;
LL z = 1, t, ans;
int p[N], x[N], cnt, s[N], L, H, mu[N], f[N], maxn = N - 7;
unordered_map<int, int> ma;
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % mod;
		a = z * a * a % mod;
		b >>= 1;
	}
	return s;
}
int getsum(int x){
	if(x <= maxn) return s[x];
	if(ma[x]) return ma[x];
	int l, r, sum = 0;
	for(l = 2; l <= x; l = r + 1){
		r = x / (x / l);
		sum = (sum + z * (r - l + 1) * getsum(x / l) % mod) % mod;
	}
	ma[x] = (1 - sum) % mod;
	return ma[x];
}
int main(){
	int i, j, n, m, l, k, r;
	mu[1] = 1;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) x[i] = p[++cnt] = i, mu[i] = -1;
		for(j = 1; j <= cnt; j++){
			t = z * i * p[j];
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
			mu[t] = -mu[i];
		}
	}
	for(i = 1; i <= maxn; i++) s[i] = s[i - 1] + mu[i];
	scanf("%d%d%d%d", &n, &k, &L, &H);
	L = (L - 1) / k + 1; L--;
	H = H / k;
	for(l = 1; l <= H; l = r + 1){
		r = min(H / (H / l), L / l? L / (L / l): inf);
		ans = (ans + z * ksm(H / l - L / l, n, mod) * (getsum(r) - getsum(l - 1)) % mod) % mod;
		//if(l >= L) printf("%d %d %d %d %d %d====\n", l, r, getsum(r), getsum(l - 1), ksm(H / l - L / l, n, mod), (getsum(r) - getsum(l - 1)) % mod);
	}
	printf("%lld", (ans % mod + mod) % mod);
	return 0;
}

第二种做法

令 $f\left(k\right)$f(k) 表示最大公约数恰好为 $k$k 且不全相同的方案数， $g\left(k\right)$g(k) 表示 最大公约数为 $k$k 且不全相同的方案数。
对于这个不全相同，我要解释一下。因为原题中 $H-L\le 10^5$H−L≤105，所以对于 $x>H-L$x>H−L， $[H,L]$[H,L] 中一定不存在两个及以上不同的数，使得他们的 $\gcd$gcd 为 $x$x，如果我们规定这些数不全相同，我们就不用考虑 $x>H-L$x>H−L 的数了，把范围缩小到了 $10^5$105。
假设 $t$t 为 $k$k 在 $[L,H]$[L,H] 之间的倍数个数，显然 $t=(\lfloor \frac{H}{x}\rfloor -\lfloor \frac{L-1}{x}\rfloor )$t=(⌊xH​⌋−⌊xL−1​⌋)
那么 $g\left(k\right)=t^N-t$g(k)=tN−t
那么最大公约数恰为 $k$k 的方案数等于最大公约数是 $k$k 倍数的方案数减去最大公约数恰为 $2k,3k,...mk$2k,3k,...mk 的方案数，即
$f\left(k\right)=g\left(k\right)-f\left(2k\right)-f\left(3k\right)-...-f\left(mk\right)$f(k)=g(k)−f(2k)−f(3k)−...−f(mk)
最后要注意，若 $L=1$L=1，所有数都可以取 $1$1
复杂度 $O(n\ln n)$O(nlnn)

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
const int mod = 1e9 + 7;
LL z = 1;
int f[N];
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
int main(){
	int i, j, n, m, x, k, L, H;
	scanf("%d%d%d%d", &n, &k, &L, &H);
	L = (L - 1) / k + 1;
	H = H / k;
	for(i = 1; i <= H - L; i++){
		x = (H / i - (L - 1) / i);
		x %= mod;
		f[i] = ((ksm(x, n, mod) - x) % mod + mod) % mod;
	}
	for(i = H - L; i >= 1; i--){
		for(j = 2; j <= (H - L) / i; j++){
			f[i] = (f[i] - f[i * j] + mod) % mod;
		}
	}
	if(L == 1) f[1] = (f[1] + 1) % mod;
	printf("%d", f[1]);
	return 0;
}