GCD(n,k)=1 C++ - 백준 11689

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

처음엔 포함 배제의 원리를 사용해 푸는 문제인 줄 알았으나

포함 배제 원리를 사용해서 푸려면 세어야 하는 경우가 너무 많아

TLE가 날 뿐더러 코드 역시 복잡하게 된다.

따라서 오일러 피함수에 대해 공부하게 되었다.

https://kimgwanjung.tistory.com/7 이 곳을 참고하였다.

처음엔 $n$을 소인수 분해하고 $p^q-p^{q-1}$ 꼴로 계속 더해나갔는데,

더 좋은 방법이 있어 소개하고자 한다.

  	ll n;
    cin >> n;
    ll res=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i) continue;
        res-=res/i;
        while(n%i==0) n/=i;
    }
    if(n>1) res-=res/n;
    cout << res;

$n\prod_{p|n}^{} (1-\frac 1p)$ 을 구하는 방법이다.

res에 $n$이 들어가고 나서 $sqrt(n)$까지 탐색하며

$n$의 소인수에 $p$에 대해 $res=res(1-\frac 1p)$로 갱신되면서

결국은 $n\prod_{p|n}^{} (1-\frac 1p)$ 꼴이 구현된다.

코드는 다음과 같다.

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

// ll sieve[1000001];

// ll solve(ll a, int b){
//     if(b==1) return a;
//     if(b==0) return 1;
//     ll k=solve(a,b/2);
//     k*=k;
//     if(b%2) k*=a;
//     return k; 
// }

// int main(){
//     ios_base::sync_with_stdio(false); cin.tie(NULL);
//     for(int i=2;i<=1000;i++){
//         if(sieve[i]!=0) continue;
//         sieve[i]=i;
//         for(int j=i*i;j<=1000000;j+=i) sieve[j]=i;
//     }
//     ll ans=1;
//     unordered_map<ll,int> um;
//     ll n;
//     cin >> n;
//     while(n!=1){
//         if(n<1000001){
//             if(sieve[n]==0) sieve[n]=n;
//             if(um.find(sieve[n])!=um.end()) um[sieve[n]]++;
//             else um[sieve[n]]=1;
//             n/=sieve[n];
//             continue;
//         }
//         int cnt=sqrt(n);
//         bool isDiv=0;
//         for(int i=2;i<=cnt;i++){
//             if(n%i==0){
//                 isDiv=1;
//                 if(um.find(i)!=um.end()) um[i]++;
//                 else um[i]=1;
//                 n/=i;
//                 break;
//             }
//         }
//         if(!isDiv){
//             if(um.find(n)!=um.end()) um[n]++;
//             else um[n]=1;
//             n=1;
//         }
//     }
//     for(auto p:um){
//         ll k=solve(p.first,p.second);
//         ans*=k-k/p.first;
//     }
//     cout << ans;
//     return 0;
// }

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n;
    cin >> n;
    ll res=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i) continue;
        res-=res/i;
        while(n%i==0) n/=i;
    }
    if(n>1) res-=res/n;
    cout << res;
    return 0;
}