[PS][정수론][서로소]/[BOJ][11689][GCD(n, k) = 1]

boj11689.cpp

#include <iostream>
#include <vector>

using namespace std;


long long n = 0;
long long ans = 0;
vector<long long> prime;

void recur(long long depth, long long mul, long long cnt) {
	if (depth == prime.size()) {
		if (cnt % 2 == 1) ans -= n / mul;
		else ans += n / mul;		
		return;
	}
	recur(depth + 1, mul * prime[depth], cnt + 1);
	recur(depth + 1, mul, cnt);
}

int main(void) {
	cin >> n;
	long long temp = n;
	for (long long i = 2; i * i <= n; i++) {
		if (temp % i == 0) {
			prime.push_back(i);
			while (temp % i == 0) temp /= i;
		}
	}
	if (temp != 1) prime.push_back(temp);
	
	recur(0, 1, 0);
	cout << ans << "\n";
	return 0;
}