洛谷P8814:解密 ← CSP-J 2022 复赛第2题

【题目来源】
https://www.luogu.com.cn/problem/P8814
https://www.acwing.com/problem/content/4732/

【题目描述】
给定一个正整数 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。

【算法分析】
(1)已知 ed=(p−1)(q−1)+1=pq−p−q+1+1,又已知 
n=pq,可得 ed=n−p−q+2,即 p+q=n-ed+2。若记 m=n-ed+2,则 p+q=m
(2)又由 (p+q)^2=p^2+2pq+q^2, (p-q)^2=p^2-2pq+q^2,可得
(p+q)^2-(p-q)^2=(p^2+2pq+q^2)-(p^2-2pq+q^2)=4pq,即 
(p−q)^2=(p+q^)2−4pq,开根号得
p-q=\pm \sqrt{(p+q)^2-4pq},即 p-q=\pm \sqrt{m^2-4n}
(3)联立可得,p=(m \pm \sqrt{m^2-4n})/2。同时,根据题目要求,p、q 必须是
正整数,若令 t=\sqrt{m^2-4n},则当 ((m+t)%2==1 || (m-t)%2==1 || m<=t) 时,无解。

【算法代码】

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
LL k,n,d,e;int main() {cin>>k;while(k--) {cin>>n>>d>>e;LL m=n-d*e+2;LL k=m*m-4*n;LL t=sqrt(k);if(t*t!=k) {cout<<"NO"<<endl;continue;}if((m+t)%2==1 || (m-t)%2==1 || m<=t) {cout<<"NO"<<endl;continue;}cout<<(m-t)/2<<" "<<(m+t)/2<<endl;}return 0;
}/*
in:
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 109out:
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
*/





【参考文献】
https://www.luogu.com.cn/problem/solution/P8814




 



 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/126898.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue中的几种name属性

vue中的几种name属性 组件名name name选项 export default{name:xxx } // 获取组件的name属性 this.$options.namevue-devtools调试工具里显示的组件名称&#xff1b; 未配置name选项&#xff0c;就是组件的文件名&#xff1b; vue3配置name通过defineOptions()函数 de…

flink cdc多种数据源安装、配置与验证

搜索 flink cdc多种数据源安装、配置与验证 文章目录 1. 前言2. 数据源安装与配置2.1 MySQL2.1.1 安装2.1.2 CDC 配置2.2 Postgresql2.2.1 安装2.2.2 CDC 配置2.3 Oracle2.3.1 安装2.3.2 CDC 配置2.4 SQLServer2.4.1 安装2.4.2 CDC 配置3. 验证3.1 Flink版本与CDC版本的对应关系…

nlp系列(7)实体识别(Bert)pytorch

模型介绍 本项目是使用Bert模型来进行文本的实体识别。 Bert模型介绍可以查看这篇文章&#xff1a;nlp系列&#xff08;2&#xff09;文本分类&#xff08;Bert&#xff09;pytorch_bert文本分类_牧子川的博客-CSDN博客 模型结构 Bert模型的模型结构&#xff1a; 数据介绍 …

MySQL——常见问题

NULL和空值的区别 1、空值不占空间&#xff0c;NULL值占空间。当字段不为NULL时&#xff0c;也可以插入空值。 2、当使用 IS NOT NULL 或者 IS NULL 时&#xff0c;只能查出字段中没有不为NULL的或者为 NULL 的&#xff0c;不能查出空值。 3、判断NULL 用IS NULL 或者 is no…

46、TCP的“三次握手”

在上一节中&#xff0c;TCP首部常用的几个选项&#xff0c;有些选项的参数就是在通信双方在建立TCP连接的时候进行确定和协商的。所以在学习过TCP报文首部之后&#xff0c;下面我们开始学习TCP的连接建立。 TCP的一个特点是提供可靠的传输机制&#xff0c;还有一个特点就是TCP…

排序(408)

一、插入排序&#xff08;直接、折半、希尔&#xff09; 【2009统考】若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果&#xff0c;则该排序算法只能是&#xff08;B&#xff09; A、冒泡排序 B、插入排序 C、选择排序 …

Elasticsearch 分布式搜索——聚合

1.聚合的种类 聚合常见的有三类&#xff1a; **桶&#xff08;Bucket&#xff09;**聚合&#xff1a;用来对文档做分组 TermAggregation&#xff1a;按照文档字段值分组&#xff0c;例如按照品牌值分组、按照国家分组Date Histogram&#xff1a;按照日期阶梯分组&#xff0c;例…

【C++】反向迭代器精讲(以list为例)

目录 二&#xff0c;全部代码 三&#xff0c;设计思路 1. 讨论 2. 关于迭代器文档一个小细节 结语 一&#xff0c;前言 如果有小伙伴还未学习普通迭代器&#xff0c;请参考这篇文章中的普通迭代器实现。 【STL】list用法&试做_底层实现_花果山~~程序猿的博客-CSDN…

Kotlin 环境下解决属性初始化问题

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

npm install依赖冲突解决办法

今天npm的时候发现报错&#xff0c;原来是依赖冲突了 npm后面加上这个指令就可以顺利的安装依赖了。问题主因就是不同开发用了不同版本node导致依赖版本不同&#xff0c;出现了成功冲突&#xff0c;这是段指令&#xff1b;它告诉npm忽略项目中引入的各个依赖模块之间依赖相同但…

【Linux系列】vmware虚拟机网络配置详解

非原创 原文地址[1] 首发博客地址[2] 系列文章地址[3] vmware 为我们提供了三种网络工作模式&#xff0c;它们分别是&#xff1a;Bridged&#xff08;桥接模式&#xff09;、NAT&#xff08;网络地址转换模式&#xff09;、Host-Only&#xff08;仅主机模式&#xff09;。 打开…

TCP原理(全网最详细)

一、确认应答&#xff08;可靠性机制&#xff09; TCP诞生的初衷就是可靠传输 可靠传输是TCP最核心的部分&#xff0c;TCP内部很多机制都是在保证可靠传输&#xff08;可以理解为发一条消息&#xff0c;上面显示已读未读&#xff0c;可靠传输就是发一条消息我知道对方是否收到…

前端实现展开收起的效果 (react)

需求背景&#xff1a;需要实现文本的展开收起效果&#xff0c;文本是一行一行的&#xff0c;数据格式是数组结构。 如图所示&#xff08;图片已脱敏&#xff09; 简单实现&#xff1a;使用一个变量控制展开收起效果。 展开收起逻辑部分&#xff08;react&#xff09; const […

C++——特殊类设计

C——特殊类设计 文章目录 C——特殊类设计特殊类设计一个类不能被拷贝设计一个类只能在堆上创建设计一个类只能在栈上创建设计一个类不能被继承 单例模式饿汉模式懒汉模式 特殊类 设计一个类不能被拷贝 拷贝只会放在两个场景&#xff0c;其一是拷贝构造函数&#xff0c;其二是…

Rocky(Centos)安装中文字体(防止中文乱码)

1、查看字体列表 运行下列命令 fc-list 若出现&#xff0c;下面截图&#xff0c;则需要安装字体管理软件 安装字体库&#xff0c;运行&#xff1a; yum -y install fontconfig 当看到下图的提示信息时说明已安装成功&#xff1a; 二、添加中文字体 1&#xff09;window…

python实现adb辅助点击屏幕工具

#!/usr/bin/env python # -*- coding: utf-8 -*-import re import os import time import subprocess import tkinter as tk from tkinter import messagebox from PIL import Image, ImageTk# 设置ADB路径&#xff08;根据你的系统和安装路径进行调整&#xff09; ADB_PATH C…

centos+jenkins+pycharm

思路&#xff1a;架构 一. 在centos上搭建jenkins环境 二. pycharm与gitee建立连接 三. 访问jenkins&#xff0c;添加任务 3.1 添加一个自由风格的任务 3.2 添加git项目路径及访问git的账号和密码 3.3 执行start.sh脚本 四. 浏览器访问jenkins执行任务

MySQL--MySQL表的增删改查(基础)

排序&#xff1a;ORDER BY 语法&#xff1a; – ASC 为升序&#xff08;从小到大&#xff09; – DESC 为降序&#xff08;从大到小&#xff09; – 默认为 ASC SELECT … FROM table_name [WHERE …] ORDER BY column [ASC|DESC], […]; *** update

半导体制造工艺(一)光刻

在这里开个新专题&#xff0c;主要详细描述半导体制造整个流程中所用到的设备工艺步骤。 在集成电路制造工艺中&#xff0c;光刻是决定集成器件集成度的核心工序&#xff0c;该工序的作用是将图形信息从掩模版&#xff08;也称掩膜版&#xff09;上保真传输、转印到半导体材料衬…

深度解析自然语言处理之篇章分析

在本文中&#xff0c;我们深入探讨了篇章分析的概念及其在自然语言处理&#xff08;NLP&#xff09;领域中的研究主题&#xff0c;以及两种先进的话语分割方法&#xff1a;基于词汇句法树的统计模型和基于BiLSTM-CRF的神经网络模型。 关注TechLead&#xff0c;分享AI全维度知识…