首页 > 代码库 > 杭电1019 Least Common Multiple【求最小公倍数】
杭电1019 Least Common Multiple【求最小公倍数】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1019
解题思路：lcm(a,b)=a*b/gcd(a,b)
反思：最开始提交的时候WA,以为是溢出了，于是改成了long long，还是WA,于是就不明白了，于是就去看了discuss，发现应该这样来写
lcm(a,b)=a*gcd(a,b)*b;是为了以防a乘以b太大溢出，注意啊！！！！所以就先除再乘。
#include<stdio.h>int gcd(int a,int b){ int t,r; if(a<b) { t=a; a=b; b=t; } r=a%b; while(r!=0) { a=b; b=r; r=a%b; } return b;}int main(){ int ncase; int n; int a; scanf("%d",&ncase); while(ncase--) { long s=1; scanf("%d",&n); while(n--) { scanf("%d",&a); s=s/gcd(s,a)*a; } printf("%ld\n",s); }}
杭电1019 Least Common Multiple【求最小公倍数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。