[C++] 2942 - 피거슨과 사과

#include <iostream>
#include <stack>
using namespace std; 

long long int gcd(long long int a, long long int b){
    // b가 0일때까지 나누기 
    
    if (b==0){
        return a;
    }
    
    else {
        return gcd(b, a%b);
    }
}
int main(){
    long long int R, G, res, n_ppl, r_num, g_num;
    cin >> R >> G;
    
    res = gcd(R, G);
    
    for (int k=1; k<res+1; k++){
        if (res%k==0){
            n_ppl = k;
            r_num = R/k;
            g_num = G/k;
            cout << n_ppl << " " << r_num << " " <<g_num<<"\n";
        }
    }
    
    
    return 0;
}

사람 수는 사과의 약수들로 나오고 이에 따라 사과를 분배하는 것을 확인할 수 있음. 그래서 최대공약수를 구해야함을 느끼고 이에 관련된 알고리즘 유클리드 호제법 적용하기. int gcd(long long int a, long long int b) 확인

 

 

아래 링크를 참고하자. 이 문제를 푸는데 꼭 필요한 개념!!

(하지만 아직 미완성..)

https://daywnme.tistory.com/323