[TIP] GCD, LCM
ユークリッドアークほう
最大公約数GCD
GCD( A , B ) = GCD( B , A%B )
if A%B == 0 -> GCD = B
else GCD( B , A%B )
最小公倍数LCM
LCM = A * B/GCD
最大公約数GCD
GCD( A , B ) = GCD( B , A%B )
if A%B == 0 -> GCD = B
else GCD( B , A%B )
最小公倍数LCM
LCM = A * B/GCD
例
// N개의 최소공배수 구하기
#include <string>
#include <vector>
using namespace std;
// 최대공약수 구하는 함수
int gcdf(int a, int b){
if(a%b == 0) return b;
return gcdf(b, a%b);
}
// 최소공배수 구하는 함수
int lcmf(int a, int b){
return a * b / gcdf(a, b);
}
int solution(vector<int> arr) {
int arrlen = arr.size(); //vector의 크기
// vector의 뒤에서부터 하나씩
for(int i = arrlen - 1; i > 0; i-- ){
// vector 의 제일 끝값 두개의 최소공배수를 구함
int lcm = lcmf(arr[i], arr[i-1]);
// 두 값을 빼고
arr.pop_back();
arr.pop_back();
// 구한 최소공배수 값을 넣는다.
arr.push_back(lcm);
}
return arr[0];
}
Reference
この問題について([TIP] GCD, LCM), 我々は、より多くの情報をここで見つけました https://velog.io/@bomine/TIP-GCD-LCMテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol