Algorithm Study_0703

동운좌와 함께하는 즐거운 알고리즘

- 최대 공약수, 최소 공배수

 

최대공약수

int gcd (int a, int b){
	return b? gcd(b, a%b): a;
}

 

최소공배수

long long lcm(int a, int b){
	return a*b/gcd(a,b);
}

 

관련 문제_백준 "분수 합" (1735)

https://www.acmicpc.net/problem/1735

1735번: 분수 합

 

- 핵심 아이디어

  x1/y1 + x2/y2 

  => UP (분자) : x1*y2 + x2*y1

       DOWN (분모) : y1*y2

 

  기약 분수로 만드는 법 : 분자와 분모를 각각 "분자와 분모의 최대공약수"로 나눈다

 

풀이 코드

#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

long long lcm(int a, int b){
    return a*b/gcd(a,b);
}

int main() {
    int x1, x2, y1, y2;
    cin>>x1>>y1; cin>>x2>>y2;
    
    int down = y1*y2;
    int up = (x1*y2+x2*y1);
    
    int g=gcd(up,down);
        
    cout<<up/g<<' '<<down/g;
    return 0;
}

 

소수 (에라토스테네스체)

void Eratos(){//소수 = false , 합성수 = true
    sieve[0]=true; sieve[1]=true;
    for(int i=2; i*i<MN; i++){
        if(sieve[i]) continue;
        for(int p=i*i; p<MN; p+=i) sieve[p]=true;
    }
}