Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Least Common Multiple"
https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_C
与えられたn個の整数の最小公倍数(LCM: least common multiple)を求めて下さい。
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #NTL_1_C : Least Common Multiple
/* Aizu Online Judge in C++ #NTL_1_C : Least Common Multiple https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_C 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ int i; while(b>0){ i=a%b; a=b; b=i; } return a; } int lcm(int a,int b){ return a*b/gcd(a,b); } int main(void){ int n; cin>>n; vector<int> a(n); cin>>a[0]; for(int i=1;i<n;i++){ cin>>a[i]; } int ans=1; for(int i=0;i<n;i++){ ans=lcm(ans,a[i]); } cout<<ans<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/