yongwonAlgo/BOJ_4355.cpp at yongwon · GDSCAlgorithm/yongwonAlgo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define  pii pair<int,int>
#define MOD 1000000000
const ll INF = 10e12;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll n = 1;
    bool flag;
    while (n != 0) {
        cin >> n;
        flag = false;
        if (n == 0) {
            return 0;
        }
        if (n == 1)
            flag = true;

        ll ans = n;
        for (ll k = 2; k <= sqrt(n); k++) {
            if (n % k == 0) {
                ans = ans - ans / k;
                while (n % k == 0)n /= k;
            }
        }
        if (n > 1)ans -= ans / n;
        if(flag) {
            cout << 0 << '\n';
        }else
        cout << ans << '\n';
    }
}