[CSP-J 2022] 解密

题意

给出 k 组询问，每组有三个正整数 n,e,d。

要求寻找正整数 $p,q$ ，满足：

n = p * q

e * d = (p - 1)(q - 1) + 1

如果存在这样的 p,q，输出它们；否则输出 NO。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> k;
    while (k--) {
        long long n, e, d;
        cin >> n >> e >> d;

        bool ok = false;
        for (long long p = 1; p * p <= n; p++) {
            if (n % p != 0) continue;
            long long q = n / p;
            if (e * d == (p - 1) * (q - 1) + 1) {
                cout << p << ' ' << q << '\n';
                ok = true;
                break;
            }
        }
        if (!ok) {
            cout << "NO\n";
        }
    }

    return 0;
}

朴素做法枚举 p，如果 p 能整除 n，就令 $q=n/p$ 再检查第二个式子。这个思路正确，但 n 可以到 $10^18$ ，即使枚举到 sqrt(n) 也太慢。

关键是把第二个式子展开：

式子	含义
$e*d = (p-1)(q-1)+1$	题目给出的条件
$e*d = pq - p - q + 2$	展开括号
$e*d = n - p - q + 2$	因为 $pq=n$
$p+q = n - e*d + 2$	得到两个数的和

令：

sum = p + q = n - e*d + 2

现在我们已经知道了 $p*q=n$ 和 $p+q=sum$ 。这说明 $p,q$ 是方程：

x^2 - sum*x + n = 0

的两个根。

所以只需要判断这个二次方程有没有正整数根。判别式为：

delta = sum^2 - 4*n

若 delta 不是非负完全平方数，就没有整数解。若 $root = sqrt(delta)$ ，则两个根只能是：

p = (sum - root) / 2

q = (sum + root) / 2

这里的 sqrt(delta) 需要得到一个整数候选根。一种写法是直接调用 sqrt 得到候选值，再回代检查 p+q 和 $p*q$ 是否正确。另一种更稳的写法是用二分求整数平方根：二分最大的 x，使得 $x*x <= delta$ 。

代码

下面保留你的写法：用 sqrt(delta) 得到候选根，再通过回代检查排除不合法情况。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/* author: Rainboy email: rainboylvx@qq.com  time: 2022年 12月 10日 星期六 10:10:31 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

long long k,n,m;
/* 定义全局变量 */
long long e,d;

#define fenc cout << "\n=================\n";

#define log(args...) { cout << "LINE:" << __LINE__ << " ";string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int main(){
    std::cin >> k;
    for(long long i=1;i<=k;++i){
        std::cin >> n >> e >> d;
        m = n- e*d+2;
        // log(m);


        //b^2-4ac
        //a = 1
        //b = -m
        //c = n
        long long dlte = m*m-4*n;
        // log(dlte);
        if( dlte < 0){
            std::cout << "NO\n" ;
        }
        else {
            long long q = (m + (long long)sqrt(dlte)) / 2;
            long long p = m-q;
            if(q > p)
                std::swap(q,p);
            if( p+q == m && p*q == n){
                std::cout << q <<" "<< p << "\n";
            }
            else
                std::cout << "NO\n" ;

        }
    }
    return 0;
}

下面是原来的整数平方根版本：不用浮点平方根，而是二分求出 root。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-10 11:39
 * update_at: 2026-07-10 11:39
 */
#include <bits/stdc++.h>
using namespace std;

long long isqrt_ll(long long x) {
    long long l = 0, r = 1000000000LL;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (mid <= x / mid) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> k;
    while (k--) {
        long long n, e, d;
        cin >> n >> e >> d;

        long long sum = n - e * d + 2;
        long long delta = sum * sum - 4 * n;
        if (delta < 0) {
            cout << "NO\n";
            continue;
        }

        long long root = isqrt_ll(delta);
        if (root * root != delta || (sum - root) % 2 != 0) {
            cout << "NO\n";
            continue;
        }

        long long p = (sum - root) / 2;
        long long q = (sum + root) / 2;
        if (p <= 0 || q <= 0 || p * q != n) {
            cout << "NO\n";
        } else {
            cout << p << ' ' << q << '\n';
        }
    }

    return 0;
}

复杂度

当前 main.cpp 每组询问只做常数次计算和检查。如果使用 main_isqrt.cpp，每组询问会二分一次整数平方根，平方根范围不超过 $10^9$ 。

main.cpp 单组时间复杂度 $O(1)$ ，总时间复杂度 $O(k)$ 。
main_isqrt.cpp 单组时间复杂度 $O(log 10^9)$ ，总时间复杂度 $O(k log 10^9)$ 。
空间复杂度 $O(1)$ 。

总结

这题看起来是在分解 n，但真正的突破口是把两个条件合起来推出 p+q。

已知两数的和与积，就可以转成一元二次方程。之后只要检查判别式是不是完全平方数，以及根是不是正整数即可。如果使用二分，它在这里不是二分答案，而是用来稳定地求整数平方根，避免浮点误差。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

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

目录

题意

思路

代码

复杂度

总结

一图流解析