發表新討論
#12373: C++函數版


jykuo1020 (ΔEΔt>=ћ/2)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 60232
來源 : [124.219.6.236]
最後登入時間 ：
2019-12-27 15:25:06
d693. 最小公倍數 | From: [103.246.208.218] | 發表日期 : 2017-07-15 18:05 
#include <iostream>

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
long long gcd(long long x,long long y){
	if(x>=y){
	  if(x%y!=0) return gcd(y,x%y);
	  else return y;}
	else {
	  if(y%x!=0) return gcd(x,y%x);
	  else return x;}
}
long long lcm(long long x,long long y){
	return (x*y)/gcd(x,y);
}
int main(int argc, char** argv) {
	long long n;
	while(cin>>n){
		if(n==0) break;
		long long a[n];cin>>a[0]>>a[1];long long w=lcm(a[0],a[1]);
	for(int i=2;i<n;i++){
		cin>>a[i];w=lcm(w,a[i]);
	}
	cout<<w<<"\n";
	}
	return 0;
}
 
#13863: Re:C++函數版


22505031 (今晚打老虎)

學校 : 國立嘉義高級中學
編號 : 68291
來源 : [140.113.236.123]
最後登入時間 ：
2024-10-16 22:09:52
d693. 最小公倍數 | From: [114.47.227.11] | 發表日期 : 2018-05-09 21:14 
#include 

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
long long gcd(long long x,long long y){
	if(x>=y){
	  if(x%y!=0) return gcd(y,x%y);
	  else return y;}
	else {
	  if(y%x!=0) return gcd(x,y%x);
	  else return x;}
}
long long lcm(long long x,long long y){
	return (x*y)/gcd(x,y);
}
int main(int argc, char** argv) {
	long long n;
	while(cin>>n){
		if(n==0) break;
		long long a[n];cin>>a[0]>>a[1];long long w=lcm(a[0],a[1]);
	for(int i=2;i<n;i++){
		cin>>a[i];w=lcm(w,a[i]);
	}
	cout<<w<<"\n";
	}
	return 0;
}




厲害 用遞迴寫輾轉相除法

!! 我沒想到用遞迴寫

 

 
#15127: Re:C++函數版


wish.rirf@gmail.com (C++ 與我)

學校 : 臺北市私立薇閣高級中學
編號 : 82132
來源 : [36.224.41.96]
最後登入時間 ：
2021-08-07 19:29:31
d693. 最小公倍數 | From: [223.136.185.164] | 發表日期 : 2018-09-15 14:40 
#include 

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
long long gcd(long long x,long long y){
	if(x>=y){
	  if(x%y!=0) return gcd(y,x%y);
	  else return y;}
	else {
	  if(y%x!=0) return gcd(x,y%x);
	  else return x;}
}
long long lcm(long long x,long long y){
	return (x*y)/gcd(x,y);
}
int main(int argc, char** argv) {
	long long n;
	while(cin>>n){
		if(n==0) break;
		long long a[n];cin>>a[0]>>a[1];long long w=lcm(a[0],a[1]);
	for(int i=2;i<n;i++){
		cin>>a[i];w=lcm(w,a[i]);
	}
	cout<<w<<"\n";
	}
	return 0;
}




厲害 用遞迴寫輾轉相除法

!! 我沒想到用遞迴寫

 


<algorithm>裡面有__gcd()

 
#18093: Re:C++函數版


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

學校 : 臺北市私立延平高級中學
編號 : 83268
來源 : [203.72.178.1]
最後登入時間 ：
2023-10-30 13:02:50
d693. 最小公倍數 | From: [114.42.215.175] | 發表日期 : 2019-06-16 15:50 
#include 

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
long long gcd(long long x,long long y){
	if(x>=y){
	  if(x%y!=0) return gcd(y,x%y);
	  else return y;}
	else {
	  if(y%x!=0) return gcd(x,y%x);
	  else return x;}
}
long long lcm(long long x,long long y){
	return (x*y)/gcd(x,y);
}
int main(int argc, char** argv) {
	long long n;
	while(cin>>n){
		if(n==0) break;
		long long a[n];cin>>a[0]>>a[1];long long w=lcm(a[0],a[1]);
	for(int i=2;i<n;i++){
		cin>>a[i];w=lcm(w,a[i]);
	}
	cout<<w<<"\n";
	}
	return 0;
}




厲害 用遞迴寫輾轉相除法

!! 我沒想到用遞迴寫

 


裡面有__gcd()


那東西很慢好嗎?

遞迴比較快

 
ZeroJudge Forum