题解 P6523【「Wdoi-1」加密通信】
Hexarhy
2021-02-26 21:40:33
### Preface
简单构造题，性质很好发现。
### Solution
「数据保证」里的两点有比较大的提示：
1. 必然存在一组解。
1. 至少有相邻的一对 $a_i$ 互不相同。
- 根据第一个条件，我们考虑 $a_i$ 一定能表示为两质数乘积。
言下之意就是她的因子只有这两个质数。
而 $a_i=b_ib_{i+1},a_{i+1}=b_{i+1}b_{i+2}$，也就是说 $\operatorname{gcd}(a_i,a_{i+1})=b_{i+1}$。
这就是一个很重要的性质。我们可以通过这个来推出其它的 $b_i$。
- 第二个条件告诉我们：
如果 $a_i=a_{i+1}$，也就是 $a_i$ 为质数的平方，此时二者的 $\text{gcd}$ 为 $1$，不适用刚才的结论。因此我们需要找到不相同的 $a_i$ 与 $a_{i+1}$，再从这个 $i$ 向前向后推答案。
- 关于无解：
其实就是某个 $b_i>m$。
~~我刚开始做很 sb，推出答案后还验证是不是素数，忘记了第一个条件，白浪费时间和码力。~~
### Code
```cpp
bool solve(void)
{
int i=1;
for(i=2;i<n;i++)
if(a[i]!=a[i-1])
{
b[i]=gcd(a[i],a[i-1]);
break;
}
for(int j=i-1;j>=1;j--) b[j]=a[j]/b[j+1];
for(int j=i+1;j<=n;j++) b[j]=a[j-1]/b[j-1];
for(int i=1;i<=n;i++) if(b[i]>m) return false;
return true;
}
```