当前位置: 首页 > news >正文

洛谷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




 



 

相关文章:

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

【题目来源】https://www.luogu.com.cn/problem/P8814https://www.acwing.com/problem/content/4732/【题目描述】 给定一个正整数 k&#xff0c;有 k 次询问&#xff0c;每次给定三个正整数 ni&#xff0c;ei&#xff0c;di&#xff0c;求两个正整数 pi&#xff0c;qi&#xf…...

Flutter实现CombineExecutor进行多个异步分组监听,监听第一个异步执行的开始和最后一个异步执行结束时机。

1.场景 我们在调用接口时&#xff0c;很多时候会同时调用多个接口&#xff0c;接口都是异步执行&#xff0c;我们很难知道调用的多个接口哪个会最后执行完成&#xff0c;我们有时候需要对最后一个接口执行完成的时机监听&#xff0c;所以基于该需求&#xff0c;设计了CombineE…...

2023 年最新Java 毕业设计选题题目参考,500道 Java 毕业设计题目,值得收藏

大家好&#xff0c;我是程序员徐师兄&#xff0c;最近有很多同学咨询&#xff0c;说毕业设计了&#xff0c;不知道选怎么题目好&#xff0c;有哪些是想需要注意的。 确实毕设选题实际上对很多同学来说一个大坑&#xff0c; 每年挖坑给自己跳的人太多太多&#xff0c;选题选得好…...

Mac电脑其他文件占用超过一大半的内存如何清理?

mac的存储空间时不时会提示内存已满&#xff0c;查看内存占用比例最大的居然是「其他文件」&#xff0c;「其他文件」是Mac无法识别的格式文件或应用插件扩展等等...如果你想要给Mac做一次彻底的磁盘空间清理&#xff0c;首当其冲可先对「其他文件」下手&#xff0c;那么我们该…...

geopandas 笔记: datasets 数据集

geopandas 自带的几个数据集 1 世界各个国家 import geopandas as gpd import pandas as pdpd.set_option(display.max_rows,None) gpd.read_file(gpd.datasets.get_path(naturalearth_lowres)) pop_est人口数量continent国家所在的大陆name国家的名称iso_a3国家的三个字母的…...

长胜证券:三大拐点共振 看好智能驾驶新一轮行情

摘要 【长胜证券&#xff1a;三大拐点共振 看好智能驾驭新一轮行情】长胜证券研报指出&#xff0c;全球共振&#xff0c;国内智驾商场正迎来三大拐点&#xff1a;1&#xff09;技能上&#xff0c;“BEV Transformer数据闭环”新架构2023年开端上车&#xff0c;使得不依靠高精地…...

AIGC专栏5——EasyPhoto AI写真照片生成器 sd-webui插件介绍、安装与使用

AIGC专栏5——EasyPhoto AI写真照片生成器 插件安装与使用 学习前言源码下载地址技术原理储备&#xff08;SD/Control/Lora&#xff09;StableDiffusionControlNetLora EasyPhoto插件简介EasyPhoto插件安装安装方式一&#xff1a;Webui界面安装 &#xff08;需要良好的网络&…...

【Python程序设计】 工厂模式【07/8】

一、说明 我们探索数据工程中使用的设计模式 - 软件设计中常见问题的可重用解决方案。 以下文章是有关 Python 数据工程系列文章的一部分&#xff0c;旨在帮助数据工程师、数据科学家、数据分析师、机器学习工程师或其他刚接触 Python 的人掌握基础知识。 迄今为止&#xff0c;…...

PHP8的多维数组-PHP8知识详解

今天分享的是php8的数组中的多维数组&#xff0c;主要内容有&#xff1a;多维数组的概念、创建和输出二维数组、创建和输出三维数组。 1、多维数组的概念 多维数组是包含一个或多个数组的数组。在多维数组中&#xff0c;主数组中的每一个元素也可以是一个数组&#xff0c;子数…...

【【STM32--28--IO引脚的复用功能】】

STM32–28–IO引脚的复用功能 STM32的IO复用功能 何为复用? 我们先了解一下何为通用 IO端口的输入或输出是由GPIO外设控制&#xff0c;我们称之为通用 复用&#xff1a; IO端口的输入或者是输出是由其他非GPIO外设控制就像经常说的USART 由 DR寄存器进行输出 STM32的IO复用功…...

CodeJock Active-X / COM v22.1.0 Crack

CodeJock Active-X / COM v22.1.0--这个支持 Unicode 啦&#xff0c; Unicode Unicode 创建专业应用程序&#xff0c;其中包含一整套高度可定制的用户界面组件&#xff0c;包括 Visual Studio 风格的对接窗格和 Office 风格的功能区、工具栏和菜单&#xff0c;为您的应用程序…...

mac通过docker搭建elasticsearch:8.9.2以及kibana:8.9.2

1.elasticsearch.yml配置修改&#xff1a; cluster.name: "docker-cluster" network.host: 0.0.0.0 http.port: 9200 #discovery.seed_hosts: ["172.17.0.2"]#----------------------- BEGIN SECURITY AUTO CONFIGURATION ----------------------- # # T…...

python实现排列组合代码

def combination(n, c, com1, limit0, per[]):for pos in range(limit, n):t per [pos]if len(set(t)) len(t):if len(t) c:yield [pos, ]else:for result in combination(n, c, com, com * pos, per [pos, ]):yield [pos, ] resultprint("排列&#xff1a;") …...

盲盒小程序开发方案

盲盒游戏作为一种富有趣味性和收藏价的虚拟盲盒产品&#xff0c;近年来在游戏市场中备受关注。本文将深入探讨盲盒游戏的开发方案&#xff0c;从市场趋势分析、用户体验设计、商业模式选择等多个维度&#xff0c;为开发者提供业且有深度的思考&#xff0c;以帮助他们在盲盒游戏…...

Mysql锁

文章目录 1. 概述2. 分类3. 全局锁4. 表级锁5. 行级锁 1. 概述 锁是计算机协调多个进程或线程并发访问某一资源的机制。在数据库中&#xff0c;除传统的计算资源&#xff08;CPU、RAM、I/O&#xff09;的争用以外&#xff0c;数据也是一种供许多用户共享的资源。如何保证数据并…...

Kubernetes(k8s)安装NFS动态供给存储类并安装KubeSphere

Kubernetes安装NFS动态供给存储类并安装KubeSphere KubeSphere介绍环境准备KubeSphereNFS动态供给 安装NFS动态供给搭建NFS下载动态供给驱动修改驱动文件安装动态供给 安装KubeSphere下载KubeSphere的yaml资源清单文件安装KubeSphere 使用KubeSphere部署应用创建项目部署MySQL …...

机器学习笔记 - 【机器学习案例】基于KerasCV的预训练模型自定义多头+多标签预测

一、KerasCV KerasCV 是一个模块化计算机视觉组件库,可与 TensorFlow、JAX 或 PyTorch 原生配合使用。这些模型、层、指标、回调等基于Keras Core构建,可以在任何框架中进行训练和序列化,并在另一个框架中重复使用,而无需进行昂贵的迁 KerasCV 可以理解为 Keras API 的水平…...

Linux Debian常用70条经典运维命令和使用案例

一、前言 今天分享一些Linux Debian运维方法以及常用命令 二、运维方法 Linux Debian系统的运维涉及到各种任务&#xff0c;包括系统安装、配置、更新和维护&#xff0c;以及故障排查和性能优化等。下面是一些常用的运维命令&#xff1a; 1、以下是部分命令注释 1. apt-ge…...

【涵子来信】——步入中学,日积跬步,以致千里

大家好&#xff1a; 我是涵子&#xff0c;好久没有发文&#xff0c;今天发个文。 如果说&#xff0c;给你一次再入中学的机会&#xff0c;你会怎么想&#xff1f;对于刚刚步入中学的我&#xff0c;目前状况尚好&#xff0c;洛谷最近刷得紧&#xff0c;看看我的洛谷。 好的&…...

【sgCreateAPI】自定义小工具:敏捷开发→自动化生成API接口脚本(接口代码生成工具)

<template><div :class"$options.name"><div class"sg-head">接口代码生成工具</div><div class"sg-container"><div class"sg-start "><div style"margin-bottom: 10px;">接口地…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...