!Функция Эйлера

Определение

Функция эйлера записывается как $\varphi (n)$ и обозначает количество чисел от 1 до $n-1$, которые являются взаимнопростыми с n.

Алгоритм подсчета

Для простого числа все просто, $\varphi (p)=p-1$. Для степени простого числа чуть посложнее, мы знаем, что $p^a$ невзаимнопросто только с числами, кратными $p$, тогда $\varphi (p^a)=p^a-p^{a-1}=p^{a-1}(p-1)$. Утверждение. Функция Эйлера мультипликативна, то есть $\varphi (ab)=\varphi (a)\varphi (b)$, если $GCD(a,b)=1$. Доказательство. Пусть $GCD(a,b)=1$. Тогда всего чисел, невзаимнопростых с $a$ - $a-\varphi (a)$, а с $b$ - $b-\varphi (b)$, тогда число будет невзаимнопростым с $ab$, если оно кратно хотя бы одному из этих двух наборов, количество таких чисел: $(a-\varphi (a))\ast b+(b-\varphi (b))\ast a-(a-\varphi (a))(b-\varphi (b))=2ab-b\varphi (a)-a\varphi (b)-ab-\varphi (a)\varphi (b)+b\varphi (a)+a\varphi (b)=ab-\varphi (a)\varphi (b)$ Тогда чтобы посчитать количество взаимнопростых с $ab$ чисел нам достаточно вычесть прошлое полученное число из $ab$: $ab-ab+\varphi (a)\varphi (b)=\varphi (a)\varphi (b)$ Отлично, теперь чтобы получить функцию Эйлера от любого $n$ нам достаточно разложить $n$ на простые числа и воспользоваться формулой для них.

Код

long long euler_func(long long x) {
	long long ans = 1;
	for (long long i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			long long cnt = 1;
			while (x % i == 0) {
				cnt *= i;
				x /= i;
			}
			cnt -= cnt / i;
			ans *= cnt;
		}
	}
	if (x != 1) {
		ans *= x - 1;
	}
	return ans;
}