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

蓝桥杯之即约分数

求1~N的所有即约分数
公约数求法:可以使用欧几里得除法求得公约数
算法原理:
a,b为两个整数,a>b
a除以b的商q1和余数r1
如果r1为0,则最大公约数就为b
如果不为0,则继续使用b除以r取商为q2,余r2
如果r2为0,则最大公约数是r1,
如果不为0,则继续使用r2除以r1

递归思想,始终是上一次的除数除以上一次的余数,然后判断是否本次余数为0否,为0,则返回除数

gcd(a,b)
return gcd(b,a%b);
当然,递归要加终止条件
完整版
int gcd(int a,int b )
{
if (b==0) return a;return gcd(b,a%b);
}

最终代码:

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b);
signed main()
{int ans=0;for(int i=1;i<=2020;i++)	{for(int j=1;j<=i;j++)//if(__gcd(i,j)==1) ans++;if(gcd(i,j)==1) ans++;}cout<<2*ans-1<<endl;return 0;}
int gcd(int a,int b )
{
if (b==0) return a;return gcd(b,a%b);
}

这里,最小公倍数就也很好计算了,
两个数相乘,除以最大公约数就是最小公倍数

改进算法

求即约分数,即要求分子与分母互质,互为质数。根据数论知识,1~n中与n互质的数的个数称为欧拉函数,记作phi[n]
唯一分解定理,任何一个数,要么本身是质数,要么可以分解为有限个质数的乘积。
根据欧拉公式和唯一分解定理,可得算法如下:

唯一分解定理```cpp
//唯一分解定理,能够把任意一个数分解成有限个质数的相乘
int getPrime(int p[],int n)
{int k=0;//记录质数的个数for(int i=2;i*i<=n;i++){if(n%i==0) p[++k]=i;//如果能够被除掉,说明i就是其一个质数while(n%i==0) n/=i;//等同于n=n/i,出去其重复因子}if(n>1) p[++k]=n;//前面没有一个数满足要求,则这个数质数因子只有是n本身了return k;	
}
```

Euler函数


```cpp
//求解欧拉函数
int getEuler(int n)
{int phi=n;int k=getPrime(P,n);for(int i=1;i<=k;i++){phi=phi-phi/P[i];}return phi;
}
```

全部代码如下:

#include<bits/stdc++.h>
using namespace std;
int P[2020]={0};
//唯一分解定理,能够把任意一个数分解成有限个质数的相乘
int getPrime(int p[],int n)
{int k=0;//记录质数的个数for(int i=2;i*i<=n;i++){if(n%i==0) p[++k]=i;//如果能够被除掉,说明i就是其一个质数while(n%i==0) n/=i;//等同于n=n/i,出去其重复因子}if(n>1) p[++k]=n;//前面没有一个数满足要求,则这个数质数因子只有是n本身了return k;	
}
//求解欧拉函数
int getEuler(int n)
{int phi=n;int k=getPrime(P,n);for(int i=1;i<=k;i++){phi=phi-phi/P[i];}return phi;
}int main()
{int ans=0;int ans1=0;ans=getPrime(P,2020);	for(int i=1;i<=2020;i++)ans1+=getEuler(i);cout<<2*ans1-1<<endl;return 0;
}

在这里插入图片描述

相关文章:

蓝桥杯之即约分数

求1~N的所有即约分数 公约数求法&#xff1a;可以使用欧几里得除法求得公约数 算法原理&#xff1a; a,b为两个整数&#xff0c;a>b a除以b的商q1和余数r1 如果r1为0&#xff0c;则最大公约数就为b 如果不为0&#xff0c;则继续使用b除以r取商为q2,余r2 如果r2为0&#xff0…...

Pointnet++改进优化器系列:全网首发Sophia优化器 |即插即用,实现有效涨点

简介:1.该教程提供大量的首发改进的方式,降低上手难度,多种结构改进,助力寻找创新点!2.本篇文章对Pointnet++特征提取模块进行改进,加入Sophia优化器,提升性能。3.专栏持续更新,紧随最新的研究内容。 目录 1.理论介绍 2.修改步骤 2.1 步骤一 2.2 步骤二 2.3...

1.27回溯(中等)

1.全排列 全排列 II 1.给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 2.给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3…...

sql管理工具archery简介

在平时的工作过程中&#xff0c;我们肯定会遇到使用sql平台的场景&#xff0c;业内也有很多工具&#xff0c;类似阿里云的dms&#xff0c;但是这个是和云厂商绑定的&#xff0c;我们可能一般没有用到阿里云组件就比较困难了&#xff0c;那还有什么选项了&#xff0c;经过调研&a…...

DEM高程地形瓦片数据Cesium使用教程

一、简介 从开始写文章到现在&#xff0c;陆续发布了全球90m、30m(包括哥白尼及ALOS)、12.5m全球级瓦片数据&#xff0c;以及中国12.5、日本10m、新西兰8m、等国家级瓦片数据&#xff0c;同时也发布了台湾20m、中国34省区12.5m等地区级瓦片数据。在数据发布的文章中对数据如何…...

3个精美的wordpress律师网站模板

暗红色WordPress律师事务所网站模板 演示 https://www.zhanyes.com/qiye/23.html 暗橙色WordPress律师网站模板 演示 https://www.zhanyes.com/qiye/18.html 红色WordPress律所网站模板 演示 https://www.zhanyes.com/qiye/22.html...

在windows环境下安装hadoop

Hadoop是一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下&#xff0c;开发分布式程序。但这个架构是基于java语言开发的&#xff0c;所以要先进行jdk的安装&#xff0c;如果电脑已经配置过jdk或者是曾经运行成功过java文件&#xff0c;那就可以跳过第一步。 …...

大数据分析组件Hive-集合数据结构

Hive的数据结构 前言一、array数组类型二、map键值对集合类型三、struct结构体类型 前言 Hive是一个基于Hadoop的数据仓库基础设施&#xff0c;用于处理大规模分布式数据集。它提供了一个类似于SQL的查询语言&#xff08;称为HiveQL&#xff09;&#xff0c;允许用户以类似于关…...

单核QPS近6000S,陌陌基于OceanBase的持久化缓存探索与实践

挚文集团于 2011 年 8 月推出了陌陌&#xff0c;这款立足地理位置服务的开放式移动视频社交应用在中国社交平台领域内独树一帜。陌陌和探探作为陌生人社交领域的主流应用&#xff0c;涵盖了多种核心业务模块&#xff0c;包括直播服务、附近动态功能、即时通讯&#xff08;IM&am…...

关于css 的基础试题

CSS是什么的缩写&#xff1f; A. Creative Style SheetsB. Cascading Style SheetsC. Computer Style SheetsD. Colorful Style Sheets 在HTML中&#xff0c;通过什么标签引入CSS样式&#xff1f; A. <script>B. <style>C. <link>D. <css> 以下哪个选项…...

Keil-C语言小总结

1、 &取地址符&#xff0c;*取地址内容 int *ptr;//声明指针 2、ptr &c; // 将c的地址赋值给指针变量ptr 3、可选参数函数 4、C宏定义 5、 memset&#xff1a;最快的数据清零函数 void *memset(void *s, int ch, size_t n); 分别是 字符串 要值的数据&#xff08;0…...

react的withRouter高阶组件:

withRouter的作用就是, 如果我们某个东西不是一个Router, 但是我们要依靠它去跳转一个页面, 比如点击页面的logo, 返回首页, 这时候就可以使用withRouter来做. 在 React Router 中&#xff0c;withRouter 是一个函数&#xff0c;用于与路由相关的组件。它接受一个组件作为参数&…...

小程序 样式 WXSS

文章目录 样式 WXSS尺⼨单位样式导⼊选择器⼩程序中使⽤less 样式 WXSS WXSS( WeiXin Style Sheets )是⼀套样式语⾔&#xff0c;⽤于描述 WXML 的组件样式。 与 CSS 相⽐&#xff0c;WXSS 扩展的特性有&#xff1a; 响应式⻓度单位 rpx样式导⼊ 尺⼨单位 rpx &#xff08;…...

LLM之RAG实战(二十一)| 使用LlamaIndex的Text2SQL和RAG的功能分析产品评论

亚马逊和沃尔玛等电子商务平台上每天都有大量的产品评论&#xff0c;这些评论是反映消费者对产品情绪的关键接触点。但是&#xff0c;企业如何从庞大的数据库获得有意义的见解&#xff1f; 我们可以使用LlamaIndex将SQL与RAG&#xff08;Retrieval Augmented Generation&#x…...

Scikit-learn (sklearn)速通 -【莫凡Python学习笔记】

视频教程链接&#xff1a;【莫烦Python】Scikit-learn (sklearn) 优雅地学会机器学习 视频教程代码 scikit-learn官网 莫烦官网学习链接 本人matplotlib、numpy、pandas笔记 1 为什么学习 Scikit learn 也简称 sklearn, 是机器学习领域当中最知名的 python 模块之一. Sk…...

支持向量机(SVM)详解

支持向量机&#xff08;support vector machines&#xff0c;SVM&#xff09;是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器&#xff0c;间隔最大使它有别于感知机。 1、线性可分支持向量机与硬间隔最大化 1.1、线性可分支持向量机 考虑一个二分…...

huggingface学习|云服务器部署Grounded-Segment-Anything:bug总会一个一个一个一个又一个的解决的

文章目录 一、环境部署&#xff08;一&#xff09;模型下载&#xff08;二&#xff09;环境配置&#xff08;三&#xff09;库的安装 二、运行&#xff08;一&#xff09; 运行grounding_dino_demo.py文件&#xff08;二&#xff09;运行grounded_sam_demo.py文件&#xff08;三…...

【最佳实践】Go 组合模式对业务解耦

在 Go 语言中&#xff0c;组合模式&#xff08;Composition&#xff09;是通过嵌入结构体&#xff08;embedding structs&#xff09;来实现的。它允许我们构建复杂的对象&#xff0c;通过将简单对象组合成树形结构来表示整个部分的层次结构。在 Go 中&#xff0c;这种模式不仅…...

arm 汇编调用C

arm64 汇编调用C函数 main.s .section .text .globl main main:stp x29, x30, [sp, -16]! //store fp x29 lr x30mov x0, #0mov x1, #1bl addmov x1, x0 // x0 return ldp x29, x30, [sp], 16 //restore fp lrretadd.c #include <stdio.h> int add(int a, int…...

Vue3+Vite使用Puppeteer进行SEO优化(SSR+Meta)

1. 背景 【笑小枫】https://www.xiaoxiaofeng.com上线啦 资源持续整合中&#xff0c;程序员必备网站&#xff0c;快点前往围观吧~ 我的个人博客【笑小枫】又一次版本大升级&#xff0c;虽然知道没有多少访问量&#xff0c;但我还是整天没事瞎折腾。因为一些功能在Halo上不太好实…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...