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