[BOJ] 정수론 및 조합론 1

📝5086번: 배수와 약수

문제 설명

배수와 약수

해결 방법

나머지 연산자를 이용한다.

💻소스코드

#include <iostream>

using namespace std;

int main()
{
    // 배수와 약수
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (true) {
        int a, b;
        cin >> a >> b;

        if (a == 0 && b == 0)
            break;
        
        if (b % a == 0)
            cout << "factor\n";
        else if (a % b == 0)
            cout << "multiple\n";
        else
            cout << "neither\n";
    }

    return 0;
}

---

📝1037: 약수

문제 설명

약수

해결 방법

1과 자기자신을 제외한 약수들을 벡터에 넣고 정렬한다. 벡터의 첫 번째 원소와 마지막 원소의 곱이 그 원소를 약수로 가지는 수가 된다.

💻소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // 약수
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, num;
    vector<int> n;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;
        n.push_back(num);
    }

    sort(n.begin(), n.end());
    cout << n[0] * n[n.size() - 1] << "\n";

    return 0;
}

---

📝2609번: 최대공약수와 최소공배수

문제 설명

최대공약수와 최소공배수

해결 방법

유클리드 호제 알고리즘을 이용해서 최대공약수를 구하고, 최대공약수를 이용해서 최소공배수를 구한다.

💻소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    int r = 0;
    int large = max(a, b);
    int small = min(a, b);
    // 유클리드 호제
    while (small) {
        r = large % small;
        large = small;
        small = r;
    }
    return large;
}

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

int main()
{
    // 최대공약수와 최소공배수
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int x, y;

    cin >> x >> y;
    cout << gcd(x, y) << "\n" << lcm(x, y);

    return 0;
}

---

📝1934번: 최소공배수

문제 설명

최소공배수

해결 방법

최소공배수는 두 수의 곱 / 최대공약수이다.

💻소스코드

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    int r = 0;
    int large = max(a, b);
    int small = min(a, b);
    // 유클리드 호제
    while (small) {
        r = large % small;
        large = small;
        small = r;
    }
    return large;
}

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

int main(void)
{
    // 최소 공배수
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    int a, b;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> a >> b;
        cout << lcm(a, b) << "\n";
    }

    return 0;
}

---

🥹📝2981번: 검문

문제 설명

검문

해결 방법

알고리즘은 다음과 같다.


셋 이상의 수가 주어졌을 때 그 수들의 최대공약수를 구하는 방법은 위와 같다.
유클리드 호제 코드는 x와 y의 크기에 상관 없이 작동된다.

💻소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int x, int y) { // 최대 공약수 구하기, 유클리드 호제
    int r;
    while (y) {
            r = x % y;
            x = y;
            y = r;
        }
    return x;
}

int main()
{
    // 검문
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, num;
    vector<int> num_vec, ans_vec;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        num_vec.push_back(num);
    }
    sort(num_vec.begin(), num_vec.end()); // 오름 차순 정렬
    int diff = num_vec[1] - num_vec[0];
    for (int i = 2; i < num_vec.size(); i++)
        diff = gcd(diff, num_vec[i] - num_vec[i - 1]); // 두 수의 차들의 최대 공약수
    ans_vec.push_back(diff);
    for (int i = 2; i * i <= diff; i++) {   // 시간 초과 방지 기법
        if (diff % i == 0) {
            ans_vec.push_back(i);
            ans_vec.push_back(diff / i);
        }
    }
    sort(ans_vec.begin(), ans_vec.end());   // 오름차순 정렬
    ans_vec.erase(unique(ans_vec.begin(), ans_vec.end()), ans_vec.end());   // 중복된 원소 제거
    for (int i = 0; i < ans_vec.size(); i++)
        cout << ans_vec[i] << ' ';  // 약수들을 오름차순으로 출력
}

---

📝3036번: 링

문제 설명

링

해결 방법

첫 번째 입력으로 받은 링이 한 바퀴 돌 때 나머지 링이 몇 바퀴 도는가를 기약분수 형태로 출력하는 문제로 해석했다. 링의 반지름을 저장하기 위해 int형 벡터를 선언했다. 두 링의 반지름의 최대공약수를 구해서 그것으로 두 링의 반지름을 각각 나눠주면 기약분수의 분자, 분모가 구해진다. 문제에서 요구하는 출력 형식에 맞게 출력해주었다.

💻소스코드

#include <iostream>
#include <vector>

using namespace std;

int gcd(int x, int y) { // 최대 공약수 구하기, 유클리드 호제 알고리즘
    int r;
    while (y) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main()
{
    // 링
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    int radius;
    vector<int> ring;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> radius;
        ring.push_back(radius);
    }
    for (int i = 1; i < N; i++) {   // 기약분수로 나타내기 위해서 최대 공약수로 두 수를 나눠줌
        int gcd_r = gcd(ring[0], ring[i]);
        int ring1 = ring[0] / gcd_r;
        int ring2 = ring[i] / gcd_r;
        cout << ring1 << '/' << ring2 << '\n'; 
    }
}

---