当前位置：首页 > news >正文

洛谷P8814：解密 ← CSP-J 2022 复赛第2题

news 2025/8/5 14:55:17

【题目来源】
https://www.luogu.com.cn/problem/P8814
https://www.acwing.com/problem/content/4732/

【题目描述】
给定一个正整数 k，有 k 次询问，每次给定三个正整数 ni，ei，di，求两个正整数 pi，qi，使 ni=pi×qi，ei×di=(pi−1)(qi−1)+1。

【输入格式】
第一行一个正整数 k，表示有 k 次询问。
接下来 k 行，第 i 行三个正整数 ni，di，ei。

【输出格式】
输出 k 行，每行两个正整数 pi，qi 表示答案。
为使输出统一，你应当保证 pi≤qi。
如果无解，请输出 NO。

【输入样例】
10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109

【输出样例】
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

【数据范围】
以下记 m=n−e×d+2。
保证对于 100% 的数据，1≤k≤10^5，对于任意的 1≤i≤k，1≤ni≤10^18，1≤ei×di≤10^18，1≤m≤10^9。

【算法分析】
（1）已知 ed=(p−1)(q−1)+1=pq−p−q+1+1，又已知 n=pq，可得 ed=n−p−q+2，即 p+q=n-ed+2。若记 m=n-ed+2，则 $p+q=m$ ；
（2）又由 (p+q)^2=p^2+2pq+q^2， (p-q)^2=p^2-2pq+q^2，可得
(p+q)^2-(p-q)^2=(p^2+2pq+q^2)-(p^2-2pq+q^2)=4pq，即 (p−q)^2=(p+q^)2−4pq，开根号得
$p-q=\pm \sqrt{(p+q)^2-4pq}$ ，即 $p-q=\pm \sqrt{m^2-4n}$
（3）联立可得， $p=(m \pm \sqrt{m^2-4n})/2$ 。同时，根据题目要求，p、q 必须是正整数，若令 $t=\sqrt{m^2-4n}$ ，则当 ((m+t)%2==1 || (m-t)%2==1 || m<=t) 时，无解。

【算法代码】

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
LL k,n,d,e;int main() {cin>>k;while(k--) {cin>>n>>d>>e;LL m=n-d*e+2;LL k=m*m-4*n;LL t=sqrt(k);if(t*t!=k) {cout<<"NO"<<endl;continue;}if((m+t)%2==1 || (m-t)%2==1 || m<=t) {cout<<"NO"<<endl;continue;}cout<<(m-t)/2<<" "<<(m+t)/2<<endl;}return 0;
}/*
in:
10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109out:
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P8814

查看全文

http://www.lryc.cn/news/160989.html