当前位置: 首页 > 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;">接口地…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

React核心概念:State是什么?如何用useState管理组件自己的数据?

系列回顾&#xff1a; 在上一篇《React入门第一步》中&#xff0c;我们已经成功创建并运行了第一个React项目。我们学会了用Vite初始化项目&#xff0c;并修改了App.jsx组件&#xff0c;让页面显示出我们想要的文字。但是&#xff0c;那个页面是“死”的&#xff0c;它只是静态…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...