信息学奥赛一本通 2087：【22CSPJ普及组】解密(decode) | 洛谷 P8814 [CSP-J 2022] 解密

【题目链接】

洛谷 P8814 [CSP-J 2022] 解密
ybt 2087：【22CSPJ普及组】解密(decode)

【题目考点】

1. 数学：一元二次方程求根

【解题思路】

输入n，d，e，满足
$n=p\ast q$
$e\ast d=(p-1)(q-1)+1$
$=p\ast q-p-q+2=n-p-q+2$
所以$p+q=n-e\ast d+2$

解法1：枚举（60分）

因此是一个二元方程组求解的问题
$p\ast q=n$
$p+q=n-e\ast 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\ast q=n$
$p+q=n-e\ast d+2$
对$p+q=n-e\ast d+2$两边乘以p，得：
$p^2+p\ast q=p(n-e\ast d+2)$
$p^2+(e\ast d-n-2)p+n=0$
对$p+q=n-e\ast d+2$两边乘以q，得：
$q^2+p\ast q=q(n-e\ast d+2)$
$q^2+(e\ast d-n-2)q+n=0$
显然p、q是一元二次方程$x^2+(e\ast d-n-2)x+n=0$的两个根。
已知一元二次方程两根分别为$\frac{-b\pm \sqrt{b^2-4ac}}{2a}$
该方程中$a=1,b=e\ast d-n-2,c=n$
因此，两根p、q为$-b\pm \sqrt{b^2-4c}$
由于p、q都是正整数，那么首先$b^2-4c$必须是完全平方数，开方后是一个正整数。同时$-b\pm \sqrt{b^2-4c}$都必须大于0。
将满足该条件的$-b\pm \sqrt{b^2-4c}$输出，先输出较小的根$-b-\sqrt{b^2-4c}$，再输出较大的跟$-b+\sqrt{b^2-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';elsecout << "NO\n";}elsecout << "NO\n";}return 0;
}