网站建设设计制作方案与价格,网站建设百度索引,浙江商城网站建设,百度信息流开户多少钱【题目链接】
洛谷 P8814 [CSP-J 2022] 解密 ybt 2087#xff1a;【22CSPJ普及组】解密(decode)
【题目考点】
1. 数学#xff1a;一元二次方程求根
【解题思路】
输入n#xff0c;d#xff0c;e#xff0c;满足 n p ∗ q np*q np∗q e ∗ d ( p − 1 ) ( q − 1…【题目链接】
洛谷 P8814 [CSP-J 2022] 解密 ybt 2087【22CSPJ普及组】解密(decode)
【题目考点】
1. 数学一元二次方程求根
【解题思路】
输入nde满足 n p ∗ q np*q np∗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-q2n-p-q2 p∗q−p−q2n−p−q2 所以 p q n − e ∗ d 2 pqn-e*d2 pqn−e∗d2
解法1枚举60分
因此是一个二元方程组求解的问题 p ∗ q n p*qn p∗qn p q n − e ∗ d 2 pqn-e*d2 pqn−e∗d2 使用枚举算法求方程组的解在输入数据较小时可以得到解。 该代码得分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(pq n-e*d2){cout p q \n;hasAns true;break;}}if(!hasAns)cout NO \n;}return 0;
}解法2一元二次方程求根
已知 p ∗ q n p*qn p∗qn p q n − e ∗ d 2 pqn-e*d2 pqn−e∗d2 对 p q n − e ∗ d 2 pqn-e*d2 pqn−e∗d2两边乘以p得 p 2 p ∗ q p ( n − e ∗ d 2 ) p^2p*qp(n-e*d2) p2p∗qp(n−e∗d2) p 2 ( e ∗ d − n − 2 ) p n 0 p^2(e*d-n-2)pn 0 p2(e∗d−n−2)pn0 对 p q n − e ∗ d 2 pqn-e*d2 pqn−e∗d2两边乘以q得 q 2 p ∗ q q ( n − e ∗ d 2 ) q^2p*qq(n-e*d2) q2p∗qq(n−e∗d2) q 2 ( e ∗ d − n − 2 ) q n 0 q^2(e*d-n-2)qn 0 q2(e∗d−n−2)qn0 显然p、q是一元二次方程 x 2 ( e ∗ d − n − 2 ) x n 0 x^2(e*d-n-2)xn0 x2(e∗d−n−2)xn0的两个根。 已知一元二次方程两根分别为 − 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 a1,be∗d−n−2,cn 因此两根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} −bb2−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 -ne*d-2;c n;delta b*b-4*c;sq sqrt(delta);if(sq*sq delta)//delta是完全平方数 {p (-b-sq)/2, q (-bsq)/2;if(p 0 q 0)cout p q \n;elsecout NO\n;}elsecout NO\n;}return 0;
}
