[BOJ][플5][17466] GCD(n, k) = 1

문제 링크

문제링크

첫 번째 풀이 : 정수론

알고리즘

포함 배제의 원리를 사용합니다.

36과 서로소인 수의 갯수를 구하는 문제입니다.

36를 소인수 분해하면 $2^2 * 3^2$입니다.

36은 2와 3의 곱으로 나타낼 수 있는데, 36이하의 수에서 2의 배수는 36/2개 3의 배수는 36/3개입니다. 그리고 6의 배수는 36/6입니다.

36과 서로소를 구하는 방법은 $36 - 36/2 - 36/3 + 36/(2*3)$입니다.

{0개 선택한 경우} - {1개 선택한 경우} + {2개 선택한 경우}를 코드로 나타내면 아래와 같습니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 101;

ll n, m;

vector<ll> prime; // n과 서로소인 갯수를 구하기 위해 약수 종류를 저장
ll ans = 0;
void recur(ll depth, ll mul, ll cnt) {
    if (depth == prime.size()) {
        if (cnt % 2 == 1) ans -= n / mul; // 홀수개 고른 경우. mul의 배수를 뺀다
        else ans += n / mul; // 짝수개 고른 경우(아무것도 선택 안한 경우 포함)
        return;
    }
    // 백트래킹 선택한다/안한다
    recur(depth + 1, mul * prime[depth], cnt + 1);
    recur(depth + 1, mul, cnt);
}

int main(void) {
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    ll temp = n;
    for (ll i = 2; i * i <= n; i++) { // n의 약수의 후보 중
        if (temp % i == 0) { // 약수는
            prime.push_back(i); // 저장
            while (temp % i == 0) temp /= i; // temp를 최소화
        }
    }
    // 나눠진 temp가 그 자체로 소수인 경우는 추가
    if (temp != 1) prime.push_back(temp);

    recur(0, 1, 0);
    cout << ans << "\n";
    return 0;
}

Success Notice: 수고하셨습니다.