求单个数的欧拉函数

ll Get_phi(ll n){
	ll ans = n;
	for(ll i = 2; i <= sqrt(n) + 1; i++){
		if(n % i == 0){
			ans = ans / i * (i - 1);
			while(n % i == 0){
				n /= i;
			}
		}
	}
	if(n > 1) ans = ans / n * (n - 1);
	return ans;
}

线性筛（同时得到欧拉函数和素数表）
代码

拓展
求[l,r]之间与n互质的数的个数（容斥原理）
转换：求[1, m]与n互质的个数
Ans = [1,r]与n互质的个数 - [1, l - 1]与n互质的个数

求解：
设n的质因数为 P 1 , P 2 , P 2 , . . . , P k P_1,P_2,P_2,...,P_k P1​,P2​,P2​,...,Pk​
设全集U = 区间[1，n]的所有数
集合 A 1 A_1 A1​由U中是 P 1 P_1 P1​倍数的数组成的
集合 A 2 A_2 A2​由U中是 P 2 P_2 P2​倍数的数组成的
…
集合 A k A_k Ak​由U中是 P k P_k Pk​倍数的数组成的
那么[1,m]与n互质的个数= ∣ U ∣ − ( ∣ A 1 ∣ + ∣ A ２ ∣ ＋ . . . + ∣ A k ∣ ) + ( ∣ A 1 交 A 2 ∣ + ∣ A 1 交 A 3 + . . . ∣ ) |U|-(|A_1| +|A_２|＋...+|A_k|) + (|A_1 交A_2| +|A1交A_3+...|) ∣U∣−(∣A1​∣+∣A２​∣＋...+∣Ak​∣)+(∣A1​交A2​∣+∣A1交A3​+...∣)
具体就是奇数个组合减，偶数个组合加。
代码实现
首先先求出n的素数因子，然后用状压枚举（1- 2 k 2^k 2k）