信奥赛-刷题笔记-二分篇-T2-P8814[CSP-J 2022] 解密0530

原创

IT从业者张某某

修改于 2025-05-31 06:36:04

18600

代码可运行

文章被收录于专栏：信奥赛-刷题笔记信奥赛-刷题笔记

运行总次数：0

代码可运行

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

二分篇题单

P8814 CSP-J 2022 解密

https://www.luogu.com.cn/problem/P8814

题目描述

给定一个正整数 k ，有 k 次询问，每次给定三个正整数 n_i, e_i, d_i ，求两个正整数 p_i, q_i ，使 n_i = p_i \times q_i 、e_i \times d_i = (p_i - 1)(q_i - 1) + 1 。

输入格式

第一行一个正整数 k ，表示有 k 次询问。

接下来 k 行，第 i 行三个正整数 n_i, d_i, e_i 。

输出格式

输出 k 行，每行两个正整数 p_i, q_i 表示答案。

为使输出统一，你应当保证 p_i \leq q_i 。

如果无解，请输出 NO。

输入输出样例 #1

输入 #1

输出 #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 \times d + 2 。

保证对于 100\% 的数据，1 \leq k \leq {10}^5 ，对于任意的 1 \leq i \leq k ，1 \leq n_i \leq {10}^{18} ，1 \leq e_i \times d_i \leq {10}^{18}

，1 \leq m \leq {10}^9 。

测试点编号	$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	无

代码1-暴力

#include<bits/stdc++.h>

using namespace std;
int k;
long long n,d,e;
 
int main(){
	cin>>k;
	while(k--){
//		cout<<k<" ";
		cin>>n>>d>>e;
		// n=p*q e*d=pq-p-q+2 = n-p-q+2;
		// p+q = n-e*d+2
		// 遍历每个p 
		int flag=0;
		for(int i=0;i<=sqrt(n);i++){
			// 遍历每个q
			for(int j=i;j<=n;j++){
				if(i*j==n && (i+j)==(n-e*d+2)){
					cout<<i<<" "<<j<<endl;
					flag=1;
					break;
				} 
			} 
			
		}
		if(flag==0) cout<<"NO"<<endl;

	}
	
	return 0;
}

代码2-暴力优化

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

int k;
long long n, d, e;

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

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

        long long s = n - d * e + 2;

        // 最大尝试到 sqrt(n)
        long long max_p = (long long)sqrtl(n) + 1;
        bool found = false;

        for (long long p = 1; p <= max_p; ++p) {
            if (n % p != 0) continue;
            long long q = n / p;

            if (p + q == s) {
                if (p <= q)
                    cout << p << " " << q << "\n";
                else
                    cout << q << " " << p << "\n";
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "NO\n";
        }
    }

    return 0;
}

输出如下：

代码3-数学推导

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    long long k;
    scanf("%lld",&k);
    while (k--) {
        long long n,e,d;
        scanf("%lld%lld%lld",&n,&e,&d);
        long long PsubQ = sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4));
        long long PaddQ = n - e * d + 2;
        long long P = (PsubQ + PaddQ) / 2;
        long long Q = PaddQ - P;
        if (P * Q == n && e * d == (P - 1) * (Q - 1) + 1 && P && Q) {
            printf("%lld %lld\n",min(P, Q),max(P, Q));
        }else {
            printf("NO\n");
        }
    }
    return 0;
}

当然可以！下面是对这段 C++ 代码的逐行解释和整体逻辑分析，帮助你理解它的功能、背后的数学原理以及潜在的问题。

📌 题目背景（CSP-J 2022：解密）

给定三个正整数 n, e, d，要求找出两个正整数 p 和 q 满足：

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

输出满足条件的 p 和 q，且保证 p <= q。若无解则输出 NO。

🧠 数学推导回顾

从公式：

e \cdot d = (p - 1)(q - 1) + 1 = pq - p - q + 2 = n - (p + q) + 2

\Rightarrow p + q = n - e \cdot d + 2

我们定义：

s = p + q = n - e*d + 2
pq = n

这是一个标准的一元二次方程问题：

x^2 - sx + n = 0

\Rightarrow x = \frac{s \pm \sqrt{s^2 - 4n}}{2}

所以只要判别式 D = s^2 - 4n 是一个完全平方数，并且解是正整数，就能得到合法的 p 和 q。

✅ 这段代码做了什么？

第一步：读取输入

long long k;
scanf("%lld",&k);
while (k--) {
    long long n,e,d;
    scanf("%lld%lld%lld",&n,&e,&d);

读取询问次数 k
每次读入 n, e, d

第二步：计算判别式和根

long long PsubQ = sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4));

这句其实是在计算：

\text{PsubQ} = \sqrt{(s)^2 - 4n}, \quad \text{其中 } s = n - ed + 2

即：

\Delta = s^2 - 4n

然后它尝试用浮点函数 sqrt() 来求这个值，并强制转为 long long 类型。

⚠️ 注意：这里存在精度丢失风险！

long long PaddQ = n - e * d + 2;

这是在计算 s = p + q

long long P = (PsubQ + PaddQ) / 2;
long long Q = PaddQ - P;

根据公式：

p = \frac{s + \sqrt{\Delta}}{2}, \quad q = s - p

第三步：验证是否合法

if (P * Q == n && e * d == (P - 1) * (Q - 1) + 1 && P && Q) {
    printf("%lld %lld\n",min(P, Q),max(P, Q));
}else {
    printf("NO\n");
}

这段代码在做以下几项检查：

P * Q == n：乘积是否等于 n
e * d == (P - 1)*(Q - 1) + 1：原始等式是否成立
P > 0 && Q > 0：确保是正整数

如果都满足，则输出 min(p, q) 和 max(p, q)；否则输出 NO

⚠️ 存在的问题

虽然这段代码看起来逻辑清晰，但有以下几个严重缺陷或潜在错误：

问题	描述
❗ 精度丢失	使用 `sqrt()` 返回 `double`，转换成 `long long` 可能导致结果不准确，不能正确判断是否是完全平方数
❗ 整除性问题	`(PsubQ + PaddQ) / 2` 不一定是整数，会导致 `P` 错误
❗ 未处理负数/非法情况	如 `s^2 < 4n` 时判别式为负，此时应直接返回 `NO`

✅ 改进建议（更鲁棒的写法）

我们可以使用一个精确的平方根函数来替代 sqrt()，并增加对奇偶性的判断：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

// 判断是否是完全平方数，并返回其平方根
long long isqrt(long long x) {
    long long r = sqrtl(x); // 先用长精度 sqrt
    while (r * r < x) ++r;
    while (r * r > x) --r;
    return r;
}

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

        long long s = n - e * d + 2;
        long long D = s * s - 4 * n;

        if (D < 0) {
            cout << "NO\n";
            continue;
        }

        long long sqD = isqrt(D);
        if (sqD * sqD != D) {
            cout << "NO\n";
            continue;
        }

        if ((s + sqD) % 2 != 0 || (s - sqD) % 2 != 0) {
            cout << "NO\n";
            continue;
        }

        long long p = (s - sqD) / 2;
        long long q = (s + sqD) / 2;

        if (p <= 0 || q <= 0 || p * q != n) {
            cout << "NO\n";
        } else {
            cout << min(p, q) << " " << max(p, q) << "\n";
        }
    }

    return 0;
}

📌 示例解析

以样例输入为例：

770 77 5
→ ed = 385
→ s = 770 - 385 + 2 = 387
→ D = 387² - 4*770 = 149769 - 3080 = 146689 = 383²
→ p = (387 - 383)/2 = 2, q = (387 + 383)/2 = 385
→ 输出：2 385

🧠 总结

内容	说明
功能	根据一元二次方程解出 `p` 和 `q`
关键公式	`p + q = s = n - ed + 2`, `pq = n`
实现方式	直接通过 `sqrt()` 解方程
缺陷	精度丢失、未判断奇偶性、未处理负判别式
推荐改进	使用 `isqrt()`、判断奇偶性、边界条件处理

🚀 小技巧优化建议

如果你希望进一步提高性能（特别是在大数据量的情况下），可以加上以下两行代码来加速 IO 操作：

ios::sync_with_stdio(false);
cin.tie(nullptr);

这两个语句会关闭 cin 和 cout 与 scanf/printf 的同步，加快输入输出速度。

如果你还有其他问题，比如想了解底层原理、调试方法、或想把这个程序改成支持多组数据等，也可以继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

登录后参与评论

0 条评论

热度