自动搬运

查看原文

来自洛谷，原作者为

	Silence_water 天天向上，追逐梦想

搬运于2025-08-24 22:28:22，当前版本为作者最后更新于2021-02-06 12:46:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

---

$Description$

给定两组正整数 $\{a,a+1,\cdots,b\}$ 和 $\{c,c+1,\cdots,d\}$。判断 $c·(c+1)\cdots d$ 能否被 $a·(a+1)\cdots b$ 整除。

---

$Analyse$

为了描述方便，令 $x=a·(a+1)\cdots b$，$y=c·(c+1)\cdots d$。

对于整除类的题目，容易想到当 $x\%y=0$ 时，对于每个在 $y$ 中出现的质因数 $p$ 必在 $x$ 中出现，且在 $x$ 中出现次数更多。那么我们可以对 $x$ 和 $y$ 进行分解质因数，然后计算质因数 $p$ 出现次数并比较。

对于本题，由于 $x$ 为多数相乘，且范围较大，考虑通过计算出质因子 $p$ 在 $b!$ 中出现的次数和在 $a-1$ 中出现的次数。那么将两者相减就是 $p$ 在 $x$ 中出现的次数。为了方便枚举质因子，这里用欧拉筛法将所有质数线性筛出。

---

$Pay~attention$

注意到 $n!$ 中质因子 $p$ 的数量等于 $1\sim n$ 中 $p$ 的数量和。

证明：（摘自 网络）

在 $1\sim n$ 中，$p$ 的倍数，即至少包含 $1$ 个质因子 $p$ 的有 $\lfloor \frac{n}{p} \rfloor$ 个。

而 $p^2$ 的倍数，即至少包含 $2$ 个质因子 $p$ 的有 $\lfloor \frac{n}{p^2}\rfloor$ 个。但其中至少包含 $1$ 个质因子已经在 $\lfloor \frac{n}{p} \rfloor$ 里统计过，所以只需要再统计第 $2$ 个质因子，即累加上 $\lfloor \frac{n}{p^2}\rfloor$，而不是 $2 \times \lfloor \frac{n}{p^2}\rfloor$。

综上所述，$n !$ 中质因子 $p$ 的个数为：

$$\lfloor \frac{n}{p}\rfloor+\lfloor \frac{n}{p^2}\rfloor+\lfloor \frac{n}{p^3}\rfloor+\lfloor \frac{n}{p^{\lfloor{\log_p} n\rfloor}}\rfloor=\sum\limits_{p^k\le n}{\lfloor \frac{n}{p^k}\rfloor} $$

---

$Solution$

欧拉筛法部分是板子，此处就不放了。

计算质因子出现次数部分如下：

int count(int x,int a)
{
	int sum=0;
	while(x)
	{
		sum+=x/a;
		x/=a;
	}
	return sum;
}

判断整除部分如下：

for(int i=1;i<=cnt&&pri[i]<=b;i++)
{
	int a_b=count(b,pri[i])-count(a-1,pri[i]);
	int c_d=count(d,pri[i])-count(c-1,pri[i]);
	if(a_b>c_d)
	{
		sol=false;
		break;
	}
}

---

$The~end$

客官看完别忘了点个赞哦~