题目链接：http://codeac.com.cn/problem/729
题解原链接http://codeac.com.cn/problem/729/solution/content/12

题目描述

给定一个正整数 kkk，有 kkk 次询问，每次给定三个正整数 ni,ei,din_i, e_i, d_ini​,ei​,di​，求两个正整数 pi,qip_i, q_ipi​,qi​，使 ni=pi×qin_i = p_i \times q_ini​=pi​×qi​、ei×di=(pi−1)(qi−1)+1e_i \times d_i = (p_i - 1)(q_i - 1) + 1ei​×di​=(pi​−1)(qi​−1)+1。

输入格式

第一行一个正整数 kkk，表示有 kkk 次询问。
接下来 kkk 行，第 iii 行三个正整数 ni,di,ein_i, d_i, e_ini​,di​,ei​。

输出格式

输出 kkk 行，每行两个正整数 pi,qip_i, q_ipi​,qi​ 表示答案。

为使输出统一，你应当保证 pi≤qip_i \leq q_ipi​≤qi​。

如果无解，请输出 NO。

解题思路

前置知识

韦达定理
在一元二次方程ax2+bx+c=0ax^2+bx+c=0ax2+bx+c=0中，两根x1,x2x_1,x_2x1​,x2​有如下关系：
x1+x2=−bax1∗x2=cax_1 + x_2 = -\frac{b}{a} \\ x_1 * x_2 = \frac{c}{a} x1​+x2​=−ab​x1​∗x2​=ac​
求根公式
在一元二次方程ax2+bx+c=0ax^2+bx+c=0ax2+bx+c=0中，两根x1,x2x_1,x_2x1​,x2​的值为:
x1,2=−b±b2−4ac2x_{1,2} = \frac{-b\pm \sqrt{b^2-4ac}}{2} x1,2​=2−b±b2−4ac​​

公式推导

已知e∗d=(p−1)(q−1)+1,n=pqe*d=(p-1)(q-1)+1, n=pqe∗d=(p−1)(q−1)+1,n=pq
ed=(p−1)(q−1)+1⟹ed=pq−p−q+2⟹ed=n−p−q+2⟹p+q=n−ed+2设m=n−ed+2ed = (p-1)(q-1)+1 \\ \implies ed = pq - p-q+2 \\ \implies ed = n - p - q + 2 \\ \implies p+q=n - ed +2 \\ 设m=n-ed+2 ed=(p−1)(q−1)+1⟹ed=pq−p−q+2⟹ed=n−p−q+2⟹p+q=n−ed+2设m=n−ed+2
故
{pq=np+q=m\begin{equation} \begin{cases} pq=n \\ p+q=m \end{cases} \end{equation} {pq=np+q=m​​​
由韦达定理的逆定理可得，p,qp,qp,q是x2−mx+n=0x^2-mx+n=0x2−mx+n=0的两根

带入求根公式得：
p=m±m2−4n2q=m±m2+4n2p=\frac{m\pm \sqrt{m^2-4n}}{2} \\ q=\frac{m\pm \sqrt{m^2+4n}}{2} p=2m±m2−4n​​q=2m±m2+4n​​
由题意p,qp,qp,q为正整数,因此需要满足下列条件：
m2−4n>0m2+4n为正整数m±m2+4n2为正整数即m±m2+4n为偶数m^2-4n>0 \\ \sqrt{m^2+4n} 为正整数 \\ \frac{m\pm \sqrt{m^2+4n}}{2} 为正整数即 {m\pm \sqrt{m^2+4n}}为偶数 m2−4n>0m2+4n​为正整数2m±m2+4n​​为正整数即m±m2+4n​为偶数
如果满足上述条件则有解，解为
p=m±m2−4n2q=m±m2+4n2p=\frac{m\pm \sqrt{m^2-4n}}{2} \\ q=\frac{m\pm \sqrt{m^2+4n}}{2} p=2m±m2−4n​​q=2m±m2+4n​​
否则无解，输出NO

代码：

#include 
#include 
using namespace std;typedef long long LL;int main() {int k;LL n, e, d;scanf("%d", &k);while (k --) {scanf("%lld%lld%lld", &n, &d, &e);LL m = n - e * d + 2;LL delta = m * m - 4 * n;LL r = sqrt(delta);if (delta < 0 || r * r != delta || (m - r) % 2) puts("NO");        else printf("%lld %lld\n", (m - r) / 2, (m + r) / 2);}return 0;
}