[CSP-J 2022] 解密 题解
一、先理解题目（不要急着抽象）
【简单理解】
这道题其实是在解决：
题目每次给我们三个数 n,d,e，要我们找两个正整数 p,q。
它们必须同时满足：
可以把它想成：
老师已经告诉你两个隐藏数字 p,q 经过计算后的结果，现在要你把这两个隐藏数字反推出去。
题目中的东西：
* k：一共有多少组询问；
* n：等于 p*q；
* d,e：用来组成第二个式子；
* p,q：我们真正要找的两个数。
最后要求：
如果存在这样的 p,q，输出较小的在前，较大的在后；如果不存在，输出 NO。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、题意抽象（从故事变成数学问题）
【抽象之后】
给定：
要求：
找到正整数 p,q，满足：
关键是：
我们不需要关心“解密”的背景，只要处理这两个等式。
本质：
这是一个“已知两个数的积和另外一个关系，反求这两个数”的数学问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、思考如何解决（先讲思考过程）
1. 最直接的方法是什么？
最直接的方法是枚举 p。
如果 p 能整除 n，那么：
再检查第二个式子是否成立。
这就是部分解。
问题是 n 最大可以到 10^18，枚举到 sqrt(n) 也可能很慢，而且询问最多有 10^5 组。
2. 观察题目特点
题目给了两个式子。
第一个式子告诉我们：
第二个式子里面也有 p,q。
如果能从第二个式子里推出 p+q，那么我们就同时知道了：
两个数的积和和都知道，就可以解出这两个数。
3. 得出算法选择
因为题目可以转化成一元二次方程，所以正解使用数学推导。
这里的一元二次方程可以理解成：
如果 p,q 是两个答案，那么它们可以看成某个方程的两个根。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、算法核心思想（重点讲理解）
先从第二个式子开始：
把括号展开：
因为：
所以：
移项得到：
令：
现在我们知道：
如果一个数 x 是 p 或 q，那么另一个数就是 m-x。
所以：
整理成：
这是一个一元二次方程。
它是否有整数解，要看判别式：
如果 delta<0，没有实数解。
如果 delta 不是完全平方数，解里会有根号，不是整数。
如果可以开平方，设：
那么：
还要保证 p,q 是正整数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、用简单例子模拟算法过程
假设：
第一步，算：
这表示：
同时题目又告诉我们：
第二步，算判别式：
第三步，开平方：
第四步，求：
检查：
所以输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、复杂度分析
部分解枚举 p，最多枚举到 sqrt(n)，单次复杂度是：
当 n 很大、询问很多时不能通过。
正解每组询问只做几次加减乘除和开平方，所以单次是：
一共有 k 组询问，总复杂度是：
可以通过 k<=10^5 的数据。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、代码实现思路
需要的变量：
* _：询问次数；
* n,d,e：题目给出的三个数；
* m：表示 p+q；
* delta：判别式；
* s：sqrt(delta)；
* p,q：最终答案。
部分解代码
正解代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、代码逐步解释
核心是这几步：
表示先算出 p+q。
用判别式判断这两个数能不能是整数。
根据两个根的公式求出 p,q。
最后再代回原式检查，是为了防止开平方误差或奇偶性不合法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、易错点总结
1. 把输入顺序看错。题目输入是 n,d,e。
2. 忘记判断 delta<0，负数不能开平方。
3. 忘记判断 delta 是不是完全平方数。
4. 忘记判断 (m-s) 能不能被 2 整除。
5. 没有最后代回检查，可能输出错误答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、最后总结解题方法
这道题考察：
数学推导、一元二次方程、整数判断。
看到这类题：
第一步：
先把题目给的式子展开。
第二步：
想办法推出 p+q 和 p*q。
第三步：
把 p,q 看成一元二次方程的两个根。
第四步：
用判别式判断能不能得到正整数解。
