洛谷-P8814 题解

前言

蒟蒻感叹！许多大佬的思路真的很复杂，于是为了部分没学过的人写了这篇题解（其实就是为了咕值），值得一看！

正文

♦算法：式子推导

从题中可得 \(\begin{cases}n_i = p_i \times q_i \\ e_i \times d_i = (p_i - 1)(q_i - 1) + 1\end{cases}\)，先拆开式子得到 \(\begin{cases} n_i = p_i \times q_i \\e_i\times d_i=p_i\times q_i-p_i-q_i+2 \end{cases}\)\(\Rightarrow \begin{cases}p_i \times q_i =n_i\\p_i+q_i=p_i\times q_i-e_i\times d_i+2\end{cases}\)\(\Rightarrow \begin{cases}p_i \times q_i =n_i\\p_i+q_i=n_i-e_i\times d_i+2\end{cases}\)，设 \(p_i+q_i=s_i\) 根据公式 \((a+b)^2-4\times a\times b=(a-b)^2\)，可以求出 \(p_i-q_i=\sqrt{{s_i}^2-4\times n_i}\)。

可得 \(\begin{cases}p_i+q_i\\p_i-q_i\end{cases}\)，易求解。

那么，如何判定原式无解？需注意题中说明 \(p_i,q_i\) 是整数，可推知 \(p_i-q_i\) 也是整数，我们知道 C++ 整数型向下取整，若开根号的值是非整数，那么 \(p_i-q_i\) 会变小，即 \(p_i\times q_i< n_i\)因此将最后求解得到的 \(p_i,q_i\) 相乘与 \(n_i\) 比较即可，若不相等，则无解。

代码：

#include<iostream>
#include<math.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
long long n,e,d,p,q,T;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>d>>e;
		long long s1=n-e*d+2;//p+q
		long long s2=sqrt(s1*s1-4*n);//p-q
		p=(s1+s2)/2,q=s1-p;
		if(p*q==n)	cout<<min(p,q)<<" "<<max(p,q)<<"\n";//题中说先大后小
		else	cout<<"NO\n";
	}
	return 0;
}

完结！

后附

日志

v1.0 on 2022.11.04: 发布