文档章节

求N个数的最小公倍数

o
 osc_n6euf5h6
发布于 2019/03/17 19:05
字数 689
阅读 31
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目描述

求n(n <= 50)个数的最小公倍数。

输入

输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数。

输出

为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。

样例输入

2 4 6
3 2 5 7

样例输出

12
70

在数学上,我们求几个数的最小公倍数的方法是对他们分解质因数,然后将他们的质因数相乘,如果有相同的质因数则乘的时候乘该共有质因数的最高次幂项,这种方法显然不适合写程序解题,我们考虑另一种方法。公式法,有这样一个公式:x*y = gcd *lcm,即是x y为要求最小公倍数的两个数,lcm代表最小公倍数,gcd代表最大公约数。将公式变形可得lcm = x*y/gcd,我们就可以利用这个公式求lcm。

求gcd的方法很多,可以手写一个函数gcd()利用辗转相除法求,由于这里是解题,我们可以直接使用G++编译器自带的 __gcd(int,int)函数来求,返回值即是这两个数的最大公约数,使用时需要包含头文件#include<algorithm>,这是c++的头文件,另外,这个函数在devc++里可用,code::blocks应该也可用,但是vs里是用不了这个函数的,请自行实现一个。

那么我们理一下写程序的思路,首先我们要用一个数组储存要求的几个数,然后写个函数循环求gcd,这里我曾犯了一个错,我把求lcm和gcd的过程分开了,就是先对这n个数求lcm,然后统一求gcd,这是错误的。正确的做法是,假如传进来n个数a b c d e....,我们应该先对a b求lcm然后求a b的gcd,再用这个结果(a b的gcd)和c一起求gcd,再用结果和d一起求gcd,以此类推。如果担心溢出问题可以将公式调整一下求值顺序,lcm = x/gcd*y,对这题而言多此一举,题目已经说明结果为32位整数。

下面是我的题解代码:

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

	int n,a;
	while(scanf("%d",&n) != EOF){
		int arr[n];
		for(int i=0;i<n;i++){
			scanf("%d",&arr[i]);
		}
		a = arr[0];
		if(n == 1){
			printf("%d\n",a);
			continue;
		}
		for(int i=1;i<n;i++){
			a = a/__gcd(a,arr[i])*arr[i];
		}
		printf("%d\n",a);
		
	}

	
	return 0;
}

这份代码提交OJ已AC。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
最大公约数(GCD)与最小公倍数(LCM)的计算

  给出两个数a、b,求最大公约数(GCD)与最小公倍数(LCM) 一、最大公约数(GCD)     代码如下,非常简单,一行就够了: 1 int GCD(int a,int b)2 {3 return a%b?GCD(b,a%b):b;4 } 二、最小...

osc_6ak2b06j
2018/04/10
2
0
蓝桥杯决赛试题:求1到n的最小公倍数

题目: 为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。 但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。 事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以...

本应坊秀策
2013/07/05
975
0
LCM性质 + 组合数 - HDU 5407 CRB and Candies

题目描述 给定一个数n,求LCM(C(n,0),C(n,1),C(n,2)...C(n,n))的值,(n<=1e6)。题目链接 解题思路 很有趣的一道数论题! 看了下网上别人的做法,什么Kummer定理我还真没听说过,仔细研究一下那...

北岛知寒
2015/08/21
0
0
[Project Euler] 来做欧拉项目练习题吧: 题目005

[Project Euler] 来做欧拉项目练习题吧: 题目005 周银辉 问题描述: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What ......

周银辉
2011/01/20
0
0
Java50道经典习题-程序6 求最大公约数及最小公倍数

题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 分析:用辗转相除法求最大公约数 两个数的最大公约数:设两个数分别为n和m,(n>=m);用定义一个变量i,使用for循环,将i的取值从m一...

osc_bquv1gtr
2019/04/30
11
0

没有更多内容

加载失败,请刷新页面

加载更多

es集群笔记

es 集群的默认配置是当集群中的某个节点磁盘达到使用率为 85% 的时候, 就不会在该节点进行创建副本, 当磁盘使用率达到 90% 的时候, 尝试将该节点的副本重分配到其他节点. 当磁盘使用率达到 ...

gaolongquan
10分钟前
4
0
VS Code编写Vue过程中出现空格不规范报错的问题

报错内容: 解决办法: 1.注释或删除这些代码 注释掉之后(重启vue服务),再进行编写的时候,空格不规范的情况下就不会再报错了。 2.如果没在webpack.dev.conf.js文件中找到注释代码就在webpack...

安然_oschina
12分钟前
9
0
域名防封_域名防红_微信域名防拦截

最近微信开始大封杀,不知道原因是什么,可能是因为违规网站太多了吧,很多网站都被错杀了,下面我们聊一下怎样才能避免域名被封杀呢。 在各种不同的域名当中,能够做出了更适合的选择,这些...

戚馨逸
16分钟前
13
0
数据结构(六)——循环链表

一、循序链表简介 1、循环链表的定义 循环链表的任意元素都有一个前驱和一个后继,所有数据元素在关系上构成逻辑上的环。 循环链表是一种特殊的单链表,尾结点的指针指向首结点的地址。 循环...

rainbowcode
19分钟前
13
0
六边形寻路格子绘制

using System.Collections;using System.Collections.Generic;using UnityEngine;public class AdventureIsland : MonoBehaviour{ static AdventureIsland instante; pu......

江湖令
20分钟前
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部