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

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

小鱼干 549 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_i、ei×di=(pi−1)(qi−1)+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 表示答案。

为使输出统一，你应当保证 pi≤qip_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.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

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

保证对于 100%100\% 的数据，1≤k≤1051 \leq k \leq {10}^5，对于任意的 1≤i≤k1 \leq i \leq k，1≤ni≤10181 \leq n_i \leq {10}^{18}，1≤ei×di≤10181 \leq e_i \times d_i \leq {10}^{18}
，1≤m≤1091 \leq m \leq {10}^9。

测试点编号 k≤k \leq n≤n \leq m≤m \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=(p−1)(q−1)+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=n−e×d+2p+q=n-e\times d +2

整理一下：{p×q=np+q=n−e×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

两边相乘并调整下位置：p2−mp+n=0p^2-mp+n=0

求解p的值即可。

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

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

若 b2−4ac<0b^2-4ac<0 则无解。

由于p为整数，所以若b±b2−4acb\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;
}
数论 CSP 题解 2022