`
phinecos
  • 浏览: 339878 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

HDU1019 Least Common Multiple

 
阅读更多

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1019

用辗转相除法求最小公倍数时要注意应该用a/y*b,若用a*b/y,则可能会数据溢出。
<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

#include<iostream>
#include
<vector>
usingnamespacestd;

intLCM(longx,longy)
{
longtemp;
longa,b;
a
=x;
b
=y;
while(x%y!=0)
{
temp
=x%y;
x
=y;
y
=temp;
}

returna/y*b;
}

voiddoProcess(vector<long>&v)
{
if(v.size()==1)
{//只有一个数据
cout<<v[0]<<endl;
return;
}

inttemp=LCM(v[0],v[1]);
for(inti=2;i<v.size();++i)
{
temp
=LCM(temp,v[i]);
}

cout
<<temp<<endl;
}

intmain()
{
intcaseNum,i,j,n,tmp;
while(cin>>caseNum)
{
for(i=0;i<caseNum;++i)
{
cin
>>n;
vector
<long>numVect;
for(j=1;j<=n;++j)
{
cin
>>tmp;
numVect.push_back(tmp);
}

doProcess(numVect);
}

}

return0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics