[保研/考研机试] KY35 最简真分数 北京大学复试上机题 C++实现
题目链接:
最简真分数
https://www.nowcoder.com/share/jump/437195121691719749588
描述
给出n个正整数,任取两个数分别作为分子和分母组成最简真分数,编程求共有几个这样的组合。
输入描述:
每组包含n(n<=600)和n个不同的整数,整数大于1且小于等于1000。
输出描述:
每行输出最简真分数组合的个数。
示例1
输入:
7 3 5 7 9 11 13 15 3 2 4 5 0
输出:
17 2
源代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;// 辗转相除法求最大公约数
int GCD(int a, int b) {if (b == 0) {return a;}else {return GCD(b, a % b);}
}int main() {int n;while (cin >> n) {if (n == 0) {break; // 输入为0时结束}vector<int> nums; // 存储输入的整数int res = 0; // 存储最简真分数的数量for (int i = 0; i < n; i++) {int temp;cin >> temp;nums.push_back(temp);}sort(nums.begin(), nums.end()); // 对输入的整数进行排序for (int i = 0; i < n; i++) {for (int j = i + 1; j < nums.size(); j++) {if (GCD(nums[i], nums[j]) == 1) {res++; // 若最大公约数为1,则说明是最简真分数,计数加1}}}cout << res << endl; // 输出最简真分数的数量}return 0;
}
思路:
-
读入整数 n,代表接下来有 n 个整数。
-
使用一个 vector 存储这 n 个整数。
-
对 vector 中的整数进行排序,方便后面的计算。
-
使用两层循环遍历所有的数对 (nums[i], nums[j]),其中 i < j。
-
对每对数分别计算最大公约数,如果最大公约数为 1,则说明这是一个最简真分数,将计数器 res 增加 1。
-
输出最终的 res 值,即最简真分数的数量。
提交结果:

编辑切换为居中
添加图片注释,不超过 140 字(可选)
相关文章:
[保研/考研机试] KY35 最简真分数 北京大学复试上机题 C++实现
题目链接: 最简真分数https://www.nowcoder.com/share/jump/437195121691719749588 描述 给出n个正整数,任取两个数分别作为分子和分母组成最简真分数,编程求共有几个这样的组合。 输入描述: 每组包含n(n<600&…...
算法备案后,企业需要做什么?合规与执行挑战
随着技术的迅猛发展,算法已经成为多数企业核心竞争力的一部分。但在技术进步的同时,我们也面临了算法透明度、公平性以及安全性的问题。因此,许多国家已经开始实施算法备案制度,以确保算法的应用满足一定的标准和规范。但在完成算…...
云原生应用程序的自动化管理和编排
云原生应用程序是一种为云环境设计的应用程序,它采用了如微服务、容器、可伸缩性和自动化等特性,以最大限度地提高效率和响应速度。本文将深入探讨云原生应用如何实现自动化管理和编排。 容器化 容器技术,如Docker,是云原生应用程…...
Spring项目整合过滤链模式~实战应用
代码下载 设计模式代码全部在gitee上,下载链接: https://gitee.com/xiaozheng2019/desgin_mode.git 日常写代码遇到的囧 1.新建一个类,不知道该放哪个包下 2.方法名称叫A,干得却是A+B+C几件事情,随时隐藏着惊喜 3.想复用一个方法,但是里面嵌套了多余的逻辑,只能自己拆出来…...
FFmpeg常见命令行(五):FFmpeg滤镜使用
前言 在Android音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》,结合我自己的工作学习经历,我准备写一个音视频系列blog。本文是音视频系…...
网络编程 tcp udp http编程流程 网络基础知识
讲解 网络基础知识网络编程tcp编程流程图示理解bind和accept函数理解监视套接字和链接套接字理解linux和window下的编程实现tcp特点 udp编程流程图示理解udp特点 http编程流程图示理解编程实现-网站服务器 网络基础知识 OSI分层:应用层 表示层 会话层 传输层 网络层…...
LaTeX基础学习笔记
LaTeX是一个文本编辑器。其类似于markdown,使用特殊标记和代码来修改文本格式,创建特殊字符等。可以使用overleaf在线LaTex编辑器编写LaTeX并转换为pdf文件(https://www.overleaf.com/) 同时推荐一个网站http://detexify.kirelab…...
zookeeper和kafka
目录 一、zookeeper理论 1.1、zookeeper定义 1.2、zookeeper工作机制 1.3、zookeeper特点 1.4、zookeeper的数据结构 1.5、zookeeper应用场景 1.6、zookeeper的选举机制 二、部署Zookeeper 集群 2.1、环境准备 2.2、安装 Zookeeper 2.3、修改配置文件 2.4、配置…...
服务器无法加载海康sdk依赖的问题
首先遇到的jna.jar和examples.jar无法加载的问题,尝试了很多方法无效,以下方法实测有效 其次是动态链接库无法加载的问题,而且是播放库,我的方法比较简单,netsdk加载出来就行了,播放库用不到,删…...
brew+nginx配置静态文件服务器
背景 一下子闲下来了,了解的我的人都知道我闲不下来。于是,我在思考COS之后,决定自己整一个本地的OSS,实现静态文件的访问。那么,首屈一指的就是我很熟的nginx。也算是个小复习吧,复习一下nginx代理静态文…...
JavaFx异常: Not on FX application thread; currentThread = Timer-0
我的定时器任务中有两个控件: FXML TextArea Display; FXML Label Label_Display; 执行下方代码会抛出:Exception in thread "Timer-0" java.lang.IllegalStateException: Not on FX application thread; currentThread Timer-0 Timer_tas…...
【Django】无法从“django.utils.encoding”导入名称“force_text”
整晚处理 Django 的导入错误。 我将把它作为提醒,希望处于相同情况的人数会减少。 原因 某些软件包版本不支持Django 4 请看下表并决定Django和Python的版本 方案 如果出现难以响应,或者更改环境麻烦,请尝试以下操作 例如出现以下错误 …...
docker-compose redis 一直启动失败
环境: centos 8.x 背景 使用docker-compose 来启动redis docker-compose.yml 如下: version: 3.3 services:redis:image: redis:latestrestart: alwayscontainer_name: redisports:- 6379:6379volumes:- ./data:/redis/data- ./redis.conf:/redis/re…...
使用GUI Guider工具在MCU上开发嵌入式GUI应用 (1) - GUI Guider简介及安装
使用GUI Guider工具在MCU上开发嵌入式GUI应用 (1) - GUI Guider简介及安装 受限于每篇文章最多只能贴9张图的限制,这个教程被拆分成了多篇文章连载发布,完整目录结构如下图x所示。后续会发布完整教程的pdf文件,敬请期待。 图x 完整教程文档…...
解决:django设置DEBUG=false时出现的问题
首先,我用的是django4.2,python3.10版本 本来,如果在settings.py中使用 DEBUG True,那么什么问题也没有,当然,这属于调试模式。 DEBUG True TEMPLATE_DEBUG DEBUGSTATIC_URL /static/ STATICFILES_DI…...
2023-08-10力扣每日一题
链接: 1289. 下降路径最小和 II 题意: 每一行选择一个数字,相邻行选择不能是同一列,求选择的数字和最小是多少 解: 每一行选择最小的次小的,下一行能加最小的(列坐标不冲突)就加…...
C#与halcon联合 缩放移动自适应图像
读取图片 //获取文件路径下的图片public HObject GetImgFromPath(string imgPath){HObject L_Img;HOperatorSet.GenEmptyObj(out L_Img);//清空图片L_Img.Dispose();//释放HOperatorSet.ReadImage(out L_Img, imgPath);//读取图片存入到l_imgreturn L_Img;}拉伸显示 //图片拉…...
推荐 4 个 yyds 的 GitHub 项目
本期推荐开源项目目录: 1. 开源的 Markdown 编辑器 2. MetaGPT 3. SuperAGI 4. 一个舒适的笔记平台 01 开源的 Markdown 编辑器 Cherry 是腾讯开源的 Markdown 编辑器,基于 Javascript具有轻量简洁、易于扩展等特点, 它可以运行在浏览器或服…...
chrome插件开发实例05-页面间通信
目录 一、页面间通信的方式 方式1: 通过消息通信...
linux安装ftp
一、安装 参考博客 https://blog.csdn.net/dafeigecsdn/article/details/126518069 rpm -qa |grep vsftpd # 查看是否安装ftp yum -y install vsftpd # 安装vsftpuseradd -d /home/lanren312 lanren312 # 指定在/home目录下创建用户 passwd lanren312 # 给用户设置密码 # 输…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
