[백준] 11689 - GCD(n, k) = 1 (c++)

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

문제 요약

N과 서로소인 수의 개수를 구해라

 

풀이 (√N)

• 정수론
• 오일러 피 함수

오일러 피 함수를 통해 서로소의 개수를 구할 수 있다. N*∏(1-1/p)  이게 식이다. 시간복잡도를 줄이기 위해 √N까지만 돌게 되는데 이렇게 돌면 소수 하나가 n에 남게 될 수 있어서 마지막에 한 번 더 처리해야 한다. 

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n,ans;cin>>n;ans=n;
    for(ll i=2;i*i<=n;i++) {
        if(n%i==0)
            ans-=ans/i;
        while(n%i==0)n/=i;
    }
    if(n>1)
        ans-=ans/n;
    cout<<ans;
}