[C++/伯俊]1934最小公倍数

8655 ワード
白駿 テキストリンク
#1934最小公倍数
https://www.acmicpc.net/problem/1934
📝問題点
  • 最大承諾数(普通/ユークリッド湖製法)
    • を求めます
  • 最小公倍数=a*b/最大公倍数
    • ハーモニー
    最大承諾数の第1種の方法を求めます
    #include <iostream>
#include <algorithm>
using namespace std;
int maxNum(int a, int b) { //최대공약수 구하는 함수
	int n = min(a, b);
	int result;
	for (int i = 1; i <= n; i++) {
		if (a % i == 0 && b % i == 0)
			result = i;
	}
	return result;
}
int main() {
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		int a, b, max;
		scanf("%d %d", &a, &b);
		max = maxNum(a, b); //최대공약수
		cout << a * b / max<<'\n';
	}
}
    最大承諾数の第2の方法を求めます(推薦して、ユークリッドの弧は法を取り除きます)
    #include <iostream>
#include <algorithm>
using namespace std;
int GCD(int a, int b){
	if (b == 0) return a;
	else return GCD(b, a % b);
}
int main() {
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		int a, b, maxNum;
		scanf("%d %d", &a, &b);
		maxNum = GCD(a, b); //최대공약수
		cout << a * b / maxNum<<'\n';
	}
}
    📝ユークリッド湖製法?
    ->2つの自然数の最大承諾数を求めるアルゴリズム
    比較対象の2つの自然数aとb(ただしa>b)aをbで割った残りの数がrの場合、GCD(a,b)=GCD(b,r)と同じであり、「rが0の場合、bは最大公約数である.」これはこの原理を利用したアルゴリズムである.
    ex)GCD(24,16)->GCD(16,8)->GCD(8,0):最大公約数=8
    注意:https://coding-factory.tistory.com/599
    IOS-appstoreのダウンロード進捗ボタンを模倣
    Pythonで処理するためのデータを読み込みます.