欧拉函数及拓展

求单个数的欧拉函数

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$P1​,P2​,P2​,...,Pk​
设全集U = 区间[1，n]的所有数
集合$A_1$A1​由U中是$P_1$P1​倍数的数组成的
集合$A_2$A2​由U中是$P_2$P2​倍数的数组成的
…
集合$A_k$Ak​由U中是$P_k$Pk​倍数的数组成的
那么[1,m]与n互质的个数=$|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$2k）