【题目描述】

给定一个正整数 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。

测试点编号	k ≤	n ≤	m ≤	特殊性质
1	10^3	10^3	10^3	保证有解
2				无
3		10^9	6 ×10^4	保证有解
4				无
5			10^9	保证有解
6				无
7	10^5	10^18		保证若有解则 p = q
8				保证有解
9				无
10

【解析】 

看到ni=pi×qi, ei×di=(pi?1)(qi?1)+1，最先想到的是枚举p和q。结合p<=q,可以枚举p从1到根号n；

可以通过60%的数据。 

详见代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    scanf("%d",&k);
    for (int i=1;i<=k;i++){
        long long n,d,e;
        scanf("%lld %lld %lld",&n,&d,&e);
        bool flag=1;
        for (long long p=1;p*p<=n;p++){
            long long q;
            if (n%p==0){
                q=n/p;
                if (d*e==(p-1)*(q-1)+1){
                    printf("%lld %lld
",p,q);
                    flag=0;
                    break;
                }
            }
        }
        if (flag==1){
            printf("NO
");
        }
    }

    return 0;
}

第7个点因为保证p=q，理论上则可以通过特判得10分（实际没测试）；

详见代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        long long n, d, e;
        scanf("%lld %lld %lld", &n, &d, &e);
        if (n > 1e9) {
            long long p, q;
            p = sqrt(n);
            q = p;
            if (n == p * q && d * e == (p - 1) * (q - 1) + 1) {
                printf("%lld %lld
", p, q);
            } else {
                printf("NO
");
            }
            return 0;
        }
        bool flag = 1;
        for (long long p = 1; p * p <= n; p++) {
            long long q;
            if (n % p == 0) {
                q = n / p;
                if (d * e == (p - 1) * (q - 1) + 1) {
                    printf("%lld %lld
", p, q);
                    flag = 0;
                    break;
                }
            }
        }
        if (flag == 1) {
            printf("NO
");
        }
    }
    return 0;
}

根据题面给的m=n?e×d+2，结合p*q=n；可推出m=p*q-(p*q-p-q+1+1)+2,即m=-(p+q)可以知道p，q为二元一次方程x^2-mx+n=0的两个根，我们只需要验证这两个根是否是整数即可；

详见代码（AC）：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    long long n, d, e, m;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        scanf("%lld %lld %lld", &n, &d, &e);
        m = n - e * d + 2;
        long long p, det;
        det = m * m - 4 * n;//德尔塔=b^2-4*a*c;
        if (det < 0) {//德尔塔小于零则无解
            printf("NO
");
            continue;
        } else {
            p = (m - sqrt(det)) / 2;//较小的那个解
            if (p * (m - p) == n && p > 0)
                printf("%lld %lld
", p, m - p);
            else
                printf("NO
");
        }
    }
    return 0;
}