【题解】[CSP-J 2022] 解密

【题解】[CSP-J 2022] 解密

小鱼干 150 2022-11-02

[CSP-J 2022] 解密

题目描述

给定一个正整数 kk,有 kk 次询问,每次给定三个正整数 ni,ei,din_i, e_i, d_i,求两个正整数 pi,qip_i, q_i,使 ni=pi×qin_i = p_i \times q_iei×di=(pi1)(qi1)+1e_i \times d_i = (p_i - 1)(q_i - 1) + 1

输入格式

第一行一个正整数 kk,表示有 kk 次询问。

接下来 kk 行,第 ii 行三个正整数 ni,di,ein_i, d_i, e_i

输出格式

输出 kk 行,每行两个正整数 pi,qip_i, q_i 表示答案。

为使输出统一,你应当保证 piqip_i \leq q_i

如果无解,请输出 NO

样例 #1

样例输入 #1

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

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

附件

【样例 #2】

见附件中的 decode/decode2.indecode/decode2.ans

【样例 #3】

见附件中的 decode/decode3.indecode/decode3.ans

【样例 #4】

见附件中的 decode/decode4.indecode/decode4.ans

【数据范围】

以下记 m=ne×d+2m = n - e \times d + 2

保证对于 100%100\% 的数据,1k1051 \leq k \leq {10}^5,对于任意的 1ik1 \leq i \leq k1ni10181 \leq n_i \leq {10}^{18}1ei×di10181 \leq e_i \times d_i \leq {10}^{18}
1m1091 \leq m \leq {10}^9

测试点编号 kk \leq nn \leq mm \leq 特殊性质
11 10310^3 10310^3 10310^3 保证有解
22 10310^3 10310^3 10310^3
33 10310^3 10910^9 6×1046\times 10^4 保证有解
44 10310^3 10910^9 6×1046\times 10^4
55 10310^3 10910^9 10910^9 保证有解
66 10310^3 10910^9 10910^9
77 10510^5 101810^{18} 10910^9 保证若有解则 p=qp=q
88 10510^5 101810^{18} 10910^9 保证有解
99 10510^5 101810^{18} 10910^9
1010 10510^5 101810^{18} 10910^9

题目分析

本题要求p与q的值。

已知的两个信息

  1. n=p×qn=p\times q
  2. e×d=(p1)(q1)+1e\times d=(p-1)(q-1)+1

展开式子2:e×d=p×q(p+q)+2=n(p+q)+2e\times d=p\times q-(p+q)+2=n-(p+q)+2

那么可得:p+q=ne×d+2p+q=n-e\times d +2

整理一下:{p×q=np+q=ne×d+2=m\left\{\begin{aligned}p\times q&=n \\p+q&=n-e\times d+2=m\end{aligned}\right.

n和m再输入后已知,那么本题就是求一元二次方程解。

根据式子1:q=npq=\frac{n}{p}

带入式子2: p+np=mp+\frac{n}{p}=m

两边相乘并调整下位置:p2mp+n=0p^2-mp+n=0

求解p的值即可。

p=b±b24ac2ap=\frac{-b\pm\sqrt{b^2-4ac}}{2a}

此时 a=1,b=m,c=na=1,b=-m,c=n

b24ac<0b^2-4ac<0 则无解。

由于p为整数,所以若b±b24acb\pm\sqrt{b^2-4ac} 无法整除 2a2a 也是无解。

其它则代入公式进行计算即可。

代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,d,e;
//p^2 -(n-e*d+2)p+n = 0
bool chk(ll num){//判断num是否时完全平方数
	ll t=ll(sqrt(num));
	return t*t==num;
}
int main(){
	int k;
	cin>>k;
	while(k--){
		cin>>n>>d>>e;
		ll b=e*d-n-2;
		ll a=1,c=n;
		if(b*b<4*a*c){
			cout<<"NO"<<endl;
		}else{
			ll t=b*b-4*a*c;
			bool f=0;
			if(chk(t)&&(ll(-b+sqrt(t))%(2*a)==0)){
				ll p=(-b-sqrt(t))/(2*a);
				ll q=n/p;
				if(p>=1){
					f=1;
					cout<<p<<" "<<q<<endl;
				}
			}
			if(!f) cout<<"NO"<<endl;
		}
	}
	return 0;
}