法 1 ， 复杂度 $O(\sqrt x)$ 。

inline ll euler(ll x) {
	ll res = x;
	for(ll i = 2; i * i <= x; i++) {
		if(x % i == 0) {
			res = res * (i - 1) / i;
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) res = res * (x - 1) / x;
	return res;
}

法 2 ，复杂度最坏 $O(x)$ 。

inline ll euler(ll x) {
	ll res = x, now = 2;
	while(x > 1) {
		if(x % now == 0) {
			res = res * (now - 1) / now;
			while(x % now == 0) x /= now;
		}
		now++;
	}
	return res;
}

数据似乎太水了？感觉构造一个比 $10^8$ 稍小一点的质数就能把我的第二种的写法求 $\varphi(x)$ 卡掉了。