自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:21:35，当前版本为作者最后更新于2020-10-05 16:00:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先要膜 $\bold{\small N\color{red}aOH\_Frog}$，另外被 Wdsr 团踢出来的蒟蒻写一下 Wdoi 题的题解/kk

社区分快掉没了/kel 求个赞，好吗？

题意简述

一段由 $n-1$ 个正整数构成的明文 $A$，对应一个由 $n$ 个质数构成的密文 $B$，对于范围内的 $i$ 满足 $B_i\times B_{i+1}=A_i$，且保证质数的范围在 $[1,M]$。

解法简析

由于整个密文是以递推的形式展现的，所以只要知道其中的一项，我们就可以很容易推知密文的内容。

其次，对于任意的一个 $A_i$，一定都是两个质数的乘积，也就是说，一个很显然的想法是对其做质因数分解。但是面向数据做题，$A_i\le 10^{18}$，所以这个想法不太现实——但是他是有启发作用的。

题目告诉我们：有至少一对 $(i,j)$，使得 $A_i \neq A_j$，这是一个突破口，因为：

$$B_{i-1}\times B_{i}=A_i\quad\large\&\normalsize\quad B_i\times B_{i+1}=A_{i+1} $$

那么怎么办呢？由于 $B_{i-1}$ 和 $B_{i+1}$ 都是质数，所以可以发现 $B_i$ 一定是 $A_i$ 和 $A_{i+1}$ 的质因数，且是最大公因数，即：

$$\gcd(A_i,A_{i+1})=B_i$$

那么我们只要找到这样的一组 $A_i$ 和 $A_{i+1}$ 并求其最大公因数 $B_i$，然后向两端进行推论，就可以得出一个可能的序列了。

因为用辗转相除法可以再 $O(\log n)$ 级别求出公因数，向两端递推的复杂度大致为 $O(n)$，最后判断答案是否存在质数不在 $[1,m]$ 区间内的情况。

代码不是很难实现，那就不放了。