信息学奥赛一本通 2087：【22CSPJ普及组】解密(decode) | 洛谷 P8814 [CSP-J 2022] 解密
【题目链接】
洛谷 P8814 [CSP-J 2022] 解密
ybt 2087：【22CSPJ普及组】解密(decode)
【题目考点】
1. 数学：一元二次方程求根
【解题思路】
输入n，d，e，满足
n
=
p
∗
q
n=p*q
n=p∗q
e
∗
d
=
(
p
−
1
)
(
q
−
1
)
+
1
e*d=(p-1)(q-1)+1
e∗d=(p−1)(q−1)+1
=
p
∗
q
−
p
−
q
+
2
=
n
−
p
−
q
+
2
=p*q-p-q+2=n-p-q+2
=p∗q−p−q+2=n−p−q+2
所以
p
+
q
=
n
−
e
∗
d
+
2
p+q=n-e*d+2
p+q=n−e∗d+2
解法1：枚举（60分）
因此是一个二元方程组求解的问题
p
∗
q
=
n
p*q=n
p∗q=n
p
+
q
=
n
−
e
∗
d
+
2
p+q=n-e*d+2
p+q=n−e∗d+2
使用枚举算法，求方程组的解，在输入数据较小时可以得到解。
该代码得分：60分。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
LL k, n, d, e;
cin >> k;
while(k--)
{
cin >> n >> d >> e;
bool hasAns = false;
for(LL p = 1; p*p <= n; ++p) if(n%p == 0)
{
LL q = n/p;
if(p+q == n-e*d+2)
{
cout << p << ' ' << q << '\n';
hasAns = true;
break;
}
}
if(!hasAns)
cout << "NO" << '\n';
}
return 0;
}
解法2：一元二次方程求根
已知
p
∗
q
=
n
p*q=n
p∗q=n
p
+
q
=
n
−
e
∗
d
+
2
p+q=n-e*d+2
p+q=n−e∗d+2
对
p
+
q
=
n
−
e
∗
d
+
2
p+q=n-e*d+2
p+q=n−e∗d+2两边乘以p，得：
p
2
+
p
∗
q
=
p
(
n
−
e
∗
d
+
2
)
p^2+p*q=p(n-e*d+2)
p2+p∗q=p(n−e∗d+2)
p
2
+
(
e
∗
d
−
n
−
2
)
p
+
n
=
0
p^2+(e*d-n-2)p+n = 0
p2+(e∗d−n−2)p+n=0
对
p
+
q
=
n
−
e
∗
d
+
2
p+q=n-e*d+2
p+q=n−e∗d+2两边乘以q，得：
q
2
+
p
∗
q
=
q
(
n
−
e
∗
d
+
2
)
q^2+p*q=q(n-e*d+2)
q2+p∗q=q(n−e∗d+2)
q
2
+
(
e
∗
d
−
n
−
2
)
q
+
n
=
0
q^2+(e*d-n-2)q+n = 0
q2+(e∗d−n−2)q+n=0
显然p、q是一元二次方程
x
2
+
(
e
∗
d
−
n
−
2
)
x
+
n
=
0
x^2+(e*d-n-2)x+n=0
x2+(e∗d−n−2)x+n=0的两个根。
已知一元二次方程两根分别为
−
b
±
b
2
−
4
a
c
2
a
\frac{-b \pm\sqrt{b^2-4ac}}{2a}
2a−b±b2−4ac
该方程中
a
=
1
,
b
=
e
∗
d
−
n
−
2
,
c
=
n
a = 1, b = e*d-n-2, c = n
a=1,b=e∗d−n−2,c=n
因此，两根p、q为
−
b
±
b
2
−
4
c
-b \pm\sqrt{b^2-4c}
−b±b2−4c
由于p、q都是正整数，那么首先
b
2
−
4
c
b^2-4c
b2−4c必须是完全平方数，开方后是一个正整数。同时
−
b
±
b
2
−
4
c
-b \pm\sqrt{b^2-4c}
−b±b2−4c都必须大于0。
将满足该条件的
−
b
±
b
2
−
4
c
-b \pm\sqrt{b^2-4c}
−b±b2−4c输出，先输出较小的根
−
b
−
b
2
−
4
c
-b -\sqrt{b^2-4c}
−b−b2−4c，再输出较大的跟
−
b
+
b
2
−
4
c
-b +\sqrt{b^2-4c}
−b+b2−4c
【题解代码】
解法2：一元二次方程求根
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
LL k, n, d, e, delta, b, c, p, q, sq;
cin >> k;
for(int i = 1; i <= k; ++i)
{
cin >> n >> d >> e;
b = -n+e*d-2;
c = n;
delta = b*b-4*c;
sq = sqrt(delta);
if(sq*sq == delta)//delta是完全平方数
{
p = (-b-sq)/2, q = (-b+sq)/2;
if(p > 0 && q > 0)
cout << p << ' ' << q << '\n';
else
cout << "NO\n";
}
else
cout << "NO\n";
}
return 0;
}
原文地址：https://blog.csdn.net/lq1990717/article/details/142714391
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！