题目

从$[L, H]$（$H-L\leq 10^5$）选出$n$个整数，使得这些数的最大公约数为$k$的方案数。

算法

首先有一个很简单的转化，原问题可以简化为：

从$[\lceil {\frac L k} \rceil, \lfloor {\frac H k} \rfloor]$中选出$n$个整数，使得这些数的最大公约数为$1$的方案数。

下面，$L$的意义不再是原题的意义了，而是$\lceil {\frac L k} \rceil$，$H$同理。

算法1

设$dp(i)$为从选出的这些数最大公约数的为$i$的方案数。那么我们可以得到：

\[dp(i)=(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n-\sum_{i|j,i < j}dp(j)
\]

然后我们就这样DP就有$80$分了，时间复杂度$O(H)$（这里的$H$不是指的是题目中的$H$，而是重新定义的$H$）。

算法2

对上面的DP进行莫比乌斯反演。

设$F(i)$为选出的数的最大公约数能够被$i$整除的方案数，那么：

\[F(i)=\sum_{i|d}dp(d)
\]

反演得：

\[dp(d)=\sum_{d|i}\mu(\frac i d) F(i)
\]

我们求的是$dp(1)$，所以$d=1$。

\[dp(1)=\sum_{i=1}^H\mu(i) F(i)=\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n
\]

这个算起来也是$O(H)$的，但是我们还可以继续化简下去。注意到题目中的条件$H-L\leq 10^5$。

当$i \geq H-(L-1)$，即$i > H - L$的时候，我们可以发现一个很神奇的东西，那就是$\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor$要么等于$0$，要么等于$1$，所以我们可以把指数去掉！

\[dp(1)=\sum_{i=1}^{H-L}\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n+\sum_{i=H-L+1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)
\]

加号左边的式子我们可以暴力算出，现在问题是右边那个怎么算。我们可以计算它的补集：

\[\sum_{i=H-L+1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)=\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)-\sum_{i=1}^{H-L}\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)
\]

减号右边的式子我们又可以暴力算出，而左边的，注意到它就是原问题，不过此时$n=1$。

原问题：$\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n$

现在我们求的：$\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)$

这样，我们的问题是：从$[L, H]$中选出$1$个整数，使得这些数的最大公约数为$1$的方案数。

这个问题的答案就是$\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)$，若$L=1$，那么式子的值就是$1$，否则就是$0$。

至此，我们就巧妙地解决这道题，时间复杂度$O(H-L)$。

代码

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long i64;

const int MAXN = (int) 1e5 + 3;

const int MOD = (int) 1e9 + 7;

int H, L, n;

int myPower(int a, int b) {

	int ans = 1;

	while (b) {

		if (b & 1)

			ans = (i64) ans * a % MOD;

		a = (i64) a * a % MOD;

		b >>= 1;

	}

	return ans;

}

int main() {

	freopen("number.in", "r", stdin);

	freopen("number.out", "w", stdout);

	int k;

	scanf("%d%d%d%d", &n, &k, &L, &H);

	L = (L + k - 1) / k;

	H = H / k;

	int HL = H - L;

	static bool notPrime[MAXN];

	static int prime[MAXN], cntPrime;

	static int mu[MAXN];

	static int fac[MAXN];

	mu[1] = 1;

	for (int i = 2; i <= HL; i ++) {

		if (! notPrime[i]) {

			prime[cntPrime ++] = i;

			mu[i] = -1;

			fac[i] = i;

		}

		for (int k = 0; k < cntPrime; k ++) {

			int j = prime[k];

			if (j > fac[i]) break;

			if ((i64) j * i > HL) break;

			notPrime[j * i] = true;

			mu[j * i] = fac[i] == j ? 0 : mu[i] * -1;

			fac[j * i] = j;

		}

	}

	i64 ans = 0;

	for (int i = 1; i <= HL; i ++) {

		ans += (i64) mu[i] * myPower(H / i - (L - 1) / i, n);

		ans %= MOD;

	}

	if (L == 1) ans ++;

	for (int i = 1; i <= HL; i ++) {

		ans -= mu[i] * (H / i - (L - 1) / i);

		ans %= MOD;

	}

	cout << (ans + MOD) % MOD << endl;

	return 0;

}

算法3

Orz

设$f(i)$为选出的数的最大公约数为$i$且选出的这些数不能全部是同一个数的方案数。

然后我们又可以得到：$$f(i)=(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n-(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)-\sum_{i|j,i < j}f(j)$$

可以发现，这里的$i$最大只有$H-L$，因为对于任意正整数$x,y(x\neq y)$，都有$gcd(x, y)\leq |x-y|$。

然后我们要加上允许全部数选同一个数的方案。

算法4

Orz

巴特西

CQOI2015 选数

题目

算法

算法1

算法2

代码

算法3

算法4

最新文章

热门文章