RE on #1 #6

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> pii;

int n, ans;
vector<pii> fac;

void dfs(int u, int d, int phi) {
	if (u == (int)fac.size()) {
		ans += n / d * phi;
		return;
	}
	dfs(u + 1, d, phi);
	d *= fac[u].first, phi *= (fac[u].first - 1);
	dfs(u + 1, d, phi);
	for (int i = 2; i <= fac[u].second; i++) {
		d *= fac[u].first, phi *= fac[u].first;
		dfs(u + 1, d, phi);
	}
}

signed main() {
	cin >> n;
	
	int t = n;
	for (int i = 2; i * i <= t; i++) {
		if (t % i == 0) {
			fac.emplace_back(i, 0);
			while (t % i == 0) t /= i, fac.back().second++;
		}
	}
	if (t != 1) {
		if (fac.back().first == t) fac.back().second++;
		else fac.emplace_back(t, 1);
	}
	
	dfs(0, 1, 1);
	
	cout << ans;	
	
	return 0;
}