GCD(n, k) = 1(11689, G1, c++)

GCD(n, k) = 1

GCD(n, k) = 1

문제

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다.

출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

풀이

암호학 문제 풀다가 지쳐서 백준을 돌고 있었는데 마침 정수론 같은 gcd 문제가 있어서 바로 풀었다.
수학을 다시 공부하게 될 줄은 몰랐는데 조금 했다고 사고력이 올라간 기분이 들긴 한다.

숫자를 입력받고, gcd(n, k) = 1을 만족하는 수를 구하라고 한다.
조금 생각하니 주어진 수를 소인수 분해한 다음 소인수중 하나를 a라고 하면 n*((a-1)/a)를 하면 된다.
왜냐하면 gcd(n, k)의 결과가 1이 아니라는 것은 k가 n의 소인수의 배수라는 것이기 때문이다.

처음에는 에라토스테네스 체로 빼줘야하나? 싶었는데 그냥 ((소인수-1)/소인수)를 곱한 것과 같은 결과가 나온다.

예를 들어 99는 3과 11을 소인수로 가진다. 그러면 99*(2/3)*(10/11) = 60으로 답이다.
숫자도 10^12밖에 되지 않기에 브포로 다 돌아도 시간안에 충분히 돌 수 있다.
set에 소인수를 다 넣고, 계산을 해주면 끝이 난다.

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int a, b, c, d;
    long long n, m, t;
    cin >> n;
    long long s_n = n;
    long long ans = n;
    set<long long> s;

    while(n>1){
        int chk = 0;
        for(long long i=2;i*i<=n;i++){
            if(n%i==0){
                s.insert(i);
                n/=i;
                chk = 1;
                break;
            }
        }
        if(!chk){
            s.insert(n);
            break;
        }
    }
    for(auto a : s){
        ans = ans/a*(a-1);
    }
    cout << ans;

    return 0;
}