如何快速求一个序列的gcd和lcm

news/2024/9/22 9:55:02

背景:
教授在打某道关于序列gcd与lcm的题,但是看不懂题解,于是决定打表找规律;然而自己又懒得算数,于是写了个程序。
使用说明:
输入格式:n str a1 a2 ... an\(n\) 为序列长度;str为操作种类,只有GCDLCM\(a\) 为序列,其中所有元素都必须是自然数。
如果输入不合法,程序会中断计算并返回错误信息;否则会直接输出答案。
代码:

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
char c[4];
long long a,b;
unsigned long long ans;
il long long gcd(long long x,long long y)
{if(!x&&!y){return 1;}if(!x){return y;}if(!y){return x;}while(1){if(x<y){swap(x,y);}x%=y;if(!x){return y;}}
}
int main()
{while(1){scanf("%s",c);if(!strcmp(c,"GCD")){scanf("%lld",&a);if(a<0){puts("ERROR: 序列大小必须是自然数");continue;}ans=0;while(a--){scanf("%lld",&b);if(b<0){puts("ERROR: 序列元素必须是自然数");break;}ans=gcd(ans,b);}if(b>=0){printf("%lld\n",ans);}continue;}if(!strcmp(c,"LCM")){scanf("%lld",&a);if(a<0){puts("ERROR: 序列大小必须是自然数");continue;}ans=1;while(a--){scanf("%lld",&b);if(b<0){puts("ERROR: 序列元素必须是自然数");break;}ans/=gcd(ans,b);ans*=b;}if(b>=0){printf("%lld\n",ans);}continue;}puts("ERROR: 操作无效");}return 0;
}
/*
in:n op a_1...a_n
0<=a<=2^32
*/

效果不错。
image

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ryyt.cn/news/57373.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

WPF check key and modified key

private void Window_KeyDown(object sender, KeyEventArgs e) {if (e.Key == Key.A && e.KeyboardDevice.Modifiers == ModifierKeys.Control){MessageBox.Show($"You entered Key:{Key.A} and modifier:{ModifierKeys.Control}");} }

数业智能心大陆告诉你如何培养孩子的批判性思维?

现今的教育体系自小学起便强调培养孩子的批判性思维,这种能力被视为在复杂世界中生存和发展的关键。在当今信息爆炸的时代,它能让我们在海量信息中辨别真伪、深入思考并做出明智决策。如今,如数业智能心大陆产出的AI 心理咨询平台的出现为培养孩子批判性思维提供了新可能,其…

maven导入本地jar

引入lib下加载(加载过后打包,以后再次使用不用再次导入) 1、首先创建一个用于创建jar包的项目,并测试能否成功运行 2、将项目打包 3、在需要引入的项目中创建lib目录 并把刚才打包的jar复制进去 4、通过dependency引入jar包groupId、artifactId、version要与jar包保持一致…

基准测试

一:基准测试1: 单线程tps能达到300/s,预估50000/s需要多少线程=50000/3002:2000个线程并发或负载持续一段时间,系统没有任何问题3;可以确定200个并发不超过1s4:可以为后续作为性能指标。 基准点 1:基准负载:线程数+Ramp+永远,用监听器tps查看拐点(第一次上升,下划点),…

查看文件(或文件夹)被哪个进程使用【文件已在另一程序中打开】

原文链接:https://www.cnblogs.com/liushui-sky/p/8135292.html windows系统中当我们在删除某个文件或文件夹时有时会提示该文件有程序在使用不能被删除,这时相当惆怅。那么可以用这个方法来找到是哪个进程在占用该文件: 1:打开任务管理器选择“性能” 2:单击下部的“资…

windows环境下使用clion编译fortran

环境配置 1.安装minGW安装之后bin目录下存在gfortran.exe配置clion环境使用安装的minGW路径工具链使用配置的minGW其他不变cmake文件编写配置完毕可能问题 没有安装minGW使用的VSstudiode

MongoDB 3种高可用架构全面剖析

大纲MongoDB 背景 高可用架构Master-Slave 模式 Replica Set 副本集模式 Sharding 模式推荐使用姿势使用姿势一:怎么保证高可用? 使用姿势二:怎么保证数据的高可靠? 使用姿势三:怎么保证数据的强一致性?总结 后记MongoDB 背景MongoDB 是一款功能完善的分布式文档数据库,…

信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、满二叉树、顶点的度、无向图、有向图

信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、满二叉树、顶点的度、无向图、有向图 PDF文档公众号回复关键字:202409061 NOIP 2014 普及组 基础题3 6 CPU、存储器、I/O 设备是通过( )连接起来的 A 接口 B 总线 C 控制线 D 系统文件…