HDOJ1019Least Common Multiple

简介: HDOJ1019Least Common Multiple

Problem Description

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.


Input

Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 … nm where m is the number of integers in the set and n1 … nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.


Output

For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.


Sample Input

2

3 5 7 15

6 4 10296 936 1287 792 1


Sample Output

105

10296


也就是求最小公倍数

/**题意:
求输入的所有数最小公倍数。
思路:
先用 欧几里德定理
求两个数的最小公倍数,所得的公倍数再与下一个数求最小公倍数。
**/
#include <stdio.h>
#include <stdlib.h>
int gcd(int a,int b)//欧几里德求最大公约数
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    int t,n,m,i,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        a=m;
        for(i=1;i<n;i++)
        {
            scanf("%d",&m);
            if(a<m)
            {
                b=a;a=m;m=b;
            }
            a=a/gcd(a,m)*m;//最小公倍数=两数之积/最大公约数
        }
        printf("%d\n",a);
    }
    return 0;
}
目录
相关文章
|
8月前
|
XML 安全 Java
Spring AOP—深入动态代理 万字详解(通俗易懂)
Spring 第四节 AOP——动态代理 万字详解!
316 24
|
12月前
|
机器学习/深度学习 人工智能 数据挖掘
阿里云云工开物助力高校的高校计划有什么用
阿里云“云工开物”高校计划旨在推动云计算技术在高校的普及与应用,通过提供云计算资源、算力支持、在线学习平台、开发者社区及数据科学竞赛等,帮助大学生提升实践能力和创新思维,培养更多创新型人才,促进校企合作。
950 2
|
机器学习/深度学习 人工智能 搜索推荐
未来人工智能在后端开发中的应用前景
随着人工智能技术的不断发展,后端开发领域也迎来了新的机遇与挑战。本文探讨了人工智能在后端开发中的应用前景,分析了其对传统开发模式的影响和未来发展趋势。
|
监控 数据挖掘 数据安全/隐私保护
ERP系统中的绩效管理与考核
【7月更文挑战第25天】 ERP系统中的绩效管理与考核
575 2
|
监控 安全 网络安全
网络安全中的网络隔离与访问控制技术
【7月更文挑战第5天】网络隔离与访问控制技术是网络安全领域的重要组成部分。通过合理的网络隔离和严格的访问控制策略,可以有效保护网络资产免受未经授权的访问和攻击。随着技术的不断发展,我们需要不断探索和创新,以应对日益复杂的网络安全威胁。
|
机器学习/深度学习 人工智能 前端开发
BladeDISC 深度学习编译器问题之在动态shape下优化整体性能如何解决
BladeDISC 深度学习编译器问题之在动态shape下优化整体性能如何解决
|
Kubernetes API 调度
在K8S中,创建一个Pod的主要流程是什么?
在K8S中,创建一个Pod的主要流程是什么?
|
Go
Golang深入浅出之-Go语言代码质量与规范:遵循Gofmt与Linting
【5月更文挑战第1天】本文讨论了如何使用`gofmt`和Lint工具提升Go代码质量。`gofmt`负责自动格式化代码,保持风格统一,而Lint工具如`golint`、`govet`、`staticcheck`则进行静态分析,检查潜在错误和未使用的变量。通过集成`gofmt`检查到CI/CD流程,避免格式冲突,并使用Lint工具发现并修复问题,如未处理的错误、不规范命名。遵循这些最佳实践,可提高代码可读性、团队协作效率和可维护性。
250 3
|
监控 算法 Java
7 种 JVM 垃圾收集器详解
7 种 JVM 垃圾收集器详解
348 0
|
数据可视化 Python
如何使用matplotlib绘制动态柱状图-python
如何使用matplotlib绘制动态柱状图-python
如何使用matplotlib绘制动态柱状图-python