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

NOIOLPJ2022B. 数学游戏 分析

数学游戏

题目描述

Kri 喜欢玩数字游戏。

一天,他在草稿纸上写下了 ttt 对正整数 (x,y)(x,y)(x,y),并对于每一对正整数计算出了 z=x×y×gcd⁡(x,y)z = x \times y \times \gcd(x,y)z=x×y×gcd(x,y)

可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的 yyy 都擦除了,还可能改动了一些 zzz

现在 Kri 想请你帮忙还原每一组的 yyy,具体地,对于每一组中的 xxxzzz ,你需要输出最小的正整数 yyy,使得 z=x×y×gcd⁡(x,y)z=x \times y \times \gcd(x,y)z=x×y×gcd(x,y)。如果这样的 yyy 不存在,也就是 Zay 一定改动了 zzz,那么请输出 −1-11

注: gcd⁡(x,y)\gcd(x,y)gcd(x,y) 表示 xxxyyy 的最大公约数,也就是最大的正整数 ddd,满足 ddd 既是 xxx 的约数,又是 yyy 的约数。

输入格式

第一行一个整数 ttt,表示有 ttt 对正整数 xxxzzz

接下来 ttt 行,每行两个正整数 xxxzzz,含义见题目描述。

输出格式

对于每对数字输出一行,如果不存在满足条件的正整数 yyy,请输出 −1-11,否则输出满足条件的最小正整数 yyy

输入数据 1

1
10 240
Copy

输出数据 1

12
Copy

样例 1 解释

x×y×gcd⁡(x,y)=10×12×gcd⁡(10,12)=240x \times y \times \gcd(x,y) = 10 \times 12 \times \gcd(10,12) = 240x×y×gcd(x,y)=10×12×gcd(10,12)=240

输入数据 2

3
5 30
4 8
11 11
Copy

输出数据 2

6
-1
1
Copy

附加样例

见样例目录下的 math3.inmath3.out ,以及 math4.inmath4.out

数据范围

对于 20%20\%20% 的数据,t,x,z≤103t,x,z \le 10^3t,x,z103

对于 40%40\%40% 的数据,t≤103,x≤106,z≤109t \le 10^3,x \le 10^6,z \le 10^9t103,x106,z109

对于另 30%30\%30% 的数据,t≤104t \le 10^4t104

对于另 20%20\%20% 的数据,x≤106x \le 10^6x106

对于 100%100\%100% 的数据,1≤t≤5×105,1≤x≤109,1≤z<2631 \le t \le 5 \times 10^5,1 \le x \le 10^9,1 \le z < 2^{63}1t5×105,1x109,1z<263

题意简述

  • 给定正整数 x,zx,zx,z,求满足 z=x×y×gcd⁡(x,y)z=x\times y\times\gcd(x,y)z=x×y×gcd(x,y) 的最小正整数 yyy,若不存在,输出 −1-11

  • 每个测试点有 ttt 次询问。

  • 1≤t≤5×1051\leq t\leq 5\times 10^51t5×1051≤x≤1091\leq x\leq 10^91x1091≤z≤2631\leq z\leq 2^{63}1z263

题目分析

方法一

x,y,zx,y,zx,y,z 中分别含有 x1,y1,z1x_1,y_1,z_1x1,y1,z1 个素因子 222,则 gcd⁡(x,y)\gcd(x,y)gcd(x,y) 中含有 min⁡(x1,y1)\min(x_1,y_1)min(x1,y1) 个素因子 222

根据条件 z=x×y×gcd⁡(x,y)z=x\times y\times\gcd(x,y)z=x×y×gcd(x,y)z1=x1+y1+min⁡(x1,y1)z_1=x_1+y_1+\min(x_1,y_1)z1=x1+y1+min(x1,y1),接着根据 x1x_1x1y1y_1y1 的大小关系进行分类讨论:

  • x1>y1x_1>y_1x1>y1
    此时 z1=x1+2y1z_1=x_1+2y_1z1=x1+2y1,且 x1>y1⇔3x1>z1x_1>y_1\Leftrightarrow 3x_1>z_1x1>y13x1>z1。注意 z1−x1z_1-x_1z1x1 必须为偶数,否则 y1y_1y1 会出现小数的情况。

  • x1≤y1x_1\leq y_1x1y1
    此时 z1=2x1+y1z_1=2x_1+y_1z1=2x1+y1,且 x1≤y1⇔3x1≤z1x_1\leq y_1\Leftrightarrow 3x_1\leq z_1x1y13x1z1

综上,y1={z1−x12=z1−x12−z12,3x1>z1z1−2x1=z1−x12−3x12,3x1≤z1=z1−x12−min⁡(3x1,z1)2y_1=\begin{cases} \dfrac{z_1-x_1}2=z_1-\dfrac{x_1}2-\dfrac{z_1}2,&3x_1>z_1\\ z_1-2x_1=z_1-\dfrac{x_1}2-\dfrac{3x_1}2,&3x_1\leq z_1 \end{cases}=z_1-\dfrac{x_1}2-\dfrac{\min(3x_1,z_1)}2y1= 2z1x1=z12x12z1,z12x1=z12x123x1,3x1>z13x1z1=z12x12min(3x1,z1)

同理,对于其他素因子,也满足上文所述。

再将这个等式转化成 x,y,zx,y,zx,y,z 的形式:

y=zx÷gcd⁡(x3,z)=zx÷gcd⁡(zx,x2)y=\dfrac z{\sqrt{x}}\div\sqrt{\gcd(x^3,z)}=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)} y=x z÷gcd(x3,z) =xz÷gcd(xz,x2)

方法二

g=gcd⁡(x,y)g=\gcd(x,y)g=gcd(x,y),得

z=xyg⇒zx=yg⇒zx=yg×g2z=xyg \Rightarrow\dfrac zx=yg \Rightarrow\dfrac zx=\dfrac yg\times g^2z=xygxz=ygxz=gy×g2

根据最大公约数性质,我们有 gcd⁡(xg,yg)=1\gcd\left(\dfrac xg,\dfrac yg\right)=1gcd(gx,gy)=1,可得

gcd⁡(zx,x2)=gcd⁡[yg×g2,(xg)2×g2]=g2⇒g=gcd⁡(zx,x2)⇒y=zx÷gcd⁡(zx,x2)\begin{aligned} &\gcd\left(\dfrac zx,x^2\right)=\gcd\left[\dfrac yg\times g^2,\left(\dfrac xg\right)^2\times g^2\right]=g^2\\ \Rightarrow&g=\sqrt{\gcd\left(\dfrac zx,x^2\right)} \Rightarrow y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}\end{aligned}gcd(xz,x2)=gcd[gy×g2,(gx)2×g2]=g2g=gcd(xz,x2) y=xz÷gcd(xz,x2)

根据上述两种方法,均可证明 y=zx÷gcd⁡(zx,x2)y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}y=xz÷gcd(xz,x2) ,故直接计算此式即可。

时间复杂度 Θ(tlog⁡x2)\Theta(t\log x^2)Θ(tlogx2)。(注意计算 gcd⁡\gcdgcd 的时间复杂度)

相关文章:

NOIOLPJ2022B. 数学游戏 分析

数学游戏 题目描述 Kri 喜欢玩数字游戏。 一天&#xff0c;他在草稿纸上写下了 ttt 对正整数 (x,y)(x,y)(x,y)&#xff0c;并对于每一对正整数计算出了 zxygcd⁡(x,y)z x \times y \times \gcd(x,y)zxygcd(x,y)。 可是调皮的 Zay 找到了 Kri 的草稿纸&#xff0c;并把每一组的…...

android studio gradle build running慢 卡住不动 失败 原因与解决方式

快速导航 分析原因解决办法 分析原因 主要原因是 gradle 构建时无法从网络获取需要的包或库。 解决办法 将国外库替换为阿里云镜像库。 例如 google 对应的库是 maven { url ‘https://maven.aliyun.com/repository/google’ }...

如何保障Facebook账号登录稳定

当谈到保障Facebook账号的稳定性时&#xff0c;我们不得不提到那些令人头疼的情况——Facebook账号被封。尽管我们已经踏入数字化的未来&#xff0c;但是被封号似乎是一个时常困扰着社交媒体用户的问题。那么&#xff0c;让我们来看看一些常见的Facebook账号被封的原因&#xf…...

当前目录下的excel文件的两列内容的相似度比较

# -- coding: utf-8 --** from sklearn.feature_extraction.text import CountVectorizer from sklearn.metrics.pairwise import cosine_similarity import numpy as np import pandas as pd import os # 获取当前目录 current_dir os.getcwd() # 获取当前目录下所有xlsx文件…...

Cookie for Mac:隐私保护工具保护您的在线隐私

随着互联网的发展&#xff0c;我们每天都会浏览各种网站&#xff0c;享受在线购物、社交娱乐和学习资料等各种便利。然而&#xff0c;您是否曾经遇到过需要频繁输入用户名和密码的情况&#xff1f;或者不方便访问您常用的网站&#xff1f;如果是这样&#xff0c;那么Cookie for…...

Huggingface训练Transformer

在之前的博客中&#xff0c;我采用SFT&#xff08;监督优化训练&#xff09;的方法训练一个GPT2的模型&#xff0c;使得这个模型可以根据提示语进行回答。具体可见博客召唤神龙打造自己的ChatGPT_gzroy的博客-CSDN博客 Huggingface提供了一个TRL的扩展库&#xff0c;可以对tra…...

IA-YOLO项目中DIP模块的初级解读

IA-YOLO项目源自论文Image-Adaptive YOLO for Object Detection in Adverse Weather Conditions&#xff0c;其提出端到端方式联合学习CNN-PP和YOLOv3&#xff0c;这确保了CNN-PP可以学习适当的DIP&#xff0c;以弱监督的方式增强图像检测。IA-YOLO方法可以自适应地处理正常和不…...

MathType7.4mac最新版本数学公式编辑器安装教程

MathType7.4中文版是一款功能强大且易于使用的公式编辑器。该软件可与word软件配合使用&#xff0c;有效提高了教学人员的工作效率&#xff0c;避免了一些数学符号和公式无法在word中输入的麻烦。新版MathType7.4启用了全新的LOGO&#xff0c;带来了更多对数学符号和公式的支持…...

为Claude的分析内容做准备:提取PDF页面内容的简易应用程序

由于Claude虽然可以分析整个文件&#xff0c;但是对文件的大小以及字数是有限制的&#xff0c;为了将pdf文件分批传入Claude人工智能分析和总结文章内容&#xff0c;才有了这篇博客&#xff1a; 在本篇博客中&#xff0c;我们将介绍一个基于 wxPython 和 PyMuPDF 库编写的简易的…...

js中作用域的理解?

1.作用域 作用域&#xff0c;即变量(变量作用域又称上下文)和函数生效(能被访问)的区域或集合 换句话说&#xff0c;作用域决定了代码区块中变量和其他资源的可见性 举个例子 function myFunction() {let inVariable "函数内部变量"; } myFunction();//要先执行这…...

机器学习基础之《分类算法(4)—案例:预测facebook签到位置》

一、背景 1、说明 2、数据集 row_id&#xff1a;签到行为的编码 x y&#xff1a;坐标系&#xff0c;人所在的位置 accuracy&#xff1a;定位的准确率 time&#xff1a;时间戳 place_id&#xff1a;预测用户将要签到的位置 3、数据集下载 https://www.kaggle.com/navoshta/gr…...

【Java】反射 之 调用方法

调用方法 我们已经能通过Class实例获取所有Field对象&#xff0c;同样的&#xff0c;可以通过Class实例获取所有Method信息。Class类提供了以下几个方法来获取Method&#xff1a; Method getMethod(name, Class...)&#xff1a;获取某个public的Method&#xff08;包括父类&a…...

Java——单例设计模式

什么是设计模式&#xff1f; 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。设计模式免去我们自己再思考和摸索。就像是经典的棋谱&#xff0c;不同的棋局&#xff0c;我们用不同的棋谱、“套路”。 经典的设计模式共有23种。…...

Java实现excel表数据的批量存储(结合easyexcel插件)

场景&#xff1a;加哥最近在做项目时&#xff0c;苦于系统自身并未提供数据批量导入的功能还不能自行添加上该功能&#xff0c;且自身不想手动一条一条将数据录入系统。随后&#xff0c;自己使用JDBC连接数据库、使用EasyExcel插件读取表格并将数据按照业务逻辑批量插入数据库完…...

Config:客户端连接服务器访问远程

springcloud-config: springcloud-config push pom <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocatio…...

【KMP算法-代码随想录】

目录 1.什么是KMP2.什么是next数组3.什么是前缀表&#xff08;1&#xff09;前后缀含义&#xff08;2&#xff09;最长公共前后缀&#xff08;3&#xff09;前缀表的必要性 4.计算前缀表5.前缀表与next数组&#xff08;1&#xff09;使用next数组来匹配 6.构造next数组&#xf…...

【手写promise——基本功能、链式调用、promise.all、promise.race】

文章目录 前言一、前置知识二、实现基本功能二、实现链式调用三、实现Promise.all四、实现Promise.race总结 前言 关于动机&#xff0c;无论是在工作还是面试中&#xff0c;都会遇到Promise的相关使用和原理&#xff0c;手写Promise也有助于学习设计模式以及代码设计。 本文主…...

计算机网络-笔记-第二章-物理层

目录 二、第二章——物理层 1、物理层的基本概念 2、物理层下面的传输媒体 &#xff08;1&#xff09;光纤、同轴电缆、双绞线、电力线【导引型】 &#xff08;2&#xff09;无线电波、微波、红外线、可见光【非导引型】 &#xff08;3&#xff09;无线电【频谱的使用】 …...

前端开发中的单伪标签清除和双伪标签清除

引言 在前端开发中&#xff0c;我们经常会遇到一些样式上的问题&#xff0c;其中之一就是伪元素造成的布局问题。为了解决这个问题&#xff0c;我们可以使用伪标签清除技术。本篇博客将介绍单伪标签清除和双伪标签清除的概念、用法和示例代码&#xff0c;并详细解释它们的原理…...

云计算中的数据安全与隐私保护策略

文章目录 1. 云计算中的数据安全挑战1.1 数据泄露和数据风险1.2 多租户环境下的隔离问题 2. 隐私保护策略2.1 数据加密2.2 访问控制和身份验证 3. 应对方法与技术3.1 零知识证明&#xff08;Zero-Knowledge Proofs&#xff09;3.2 同态加密&#xff08;Homomorphic Encryption&…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...