题解 P6523 【「Wdoi-1」加密通信】

· · 题解

首先要膜 \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] 区间内的情况。

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