“下一个就是你了，承太郎“
定义
指的是满足小于等于$N$且与$N$互质的数目和。
用 $\varphi(N)$ 来表示。
欧拉公式求解
对于一个正整数$N$满足：
$\varphi(x)=\sum_{k}[(k, n)=1][k \in N][k<n]$
则有
$\varphi(n)=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\left(1-\frac{1}{p_{3}}\right) \cdots\left(1-\frac{1}{p_{k}}\right)$
有 $N=\prod p_i^{c_i}$ ，则有 $\varphi(N)=N\times\prod \frac{p_i+1}{p_i}$ 。
欧拉函数的性质：
当 $N=0$ 时
$\varphi(0)=0$.
当 $N=1$ 时
$\varphi(1)=1$.因为1与自身互质。
当 $N$ 为质数时
$\varphi(N)=N-1$.
如果 $ P$ 是质数，而 $N$ 是 $P$ 的正整数次方
$\varphi(P^N)=P^N(1-\frac{1}{p})$
欧拉定理
设$a,m \in N^+$，且$(a,m)=1$，那么则有
$a^{\varphi(m)} \equiv 1 \pmod m$
且$a$对模$m$的阶$\delta_m(a)$必须整除$\varphi(a)$.
证明：
取模$m$的缩系，$a_1,a_2,a_3……a_{\varphi(m)}$，
则$aa_1,aa_2,aa_3……aa_{\varphi(m)}$也是$m$的缩系.
故有$\prod_{i=1}^{\varphi(m)}a_i \equiv \prod_{i=1}^{\varphi(m)}aa_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)}a_i \pmod m$
则可以推出$a^{\varphi(m)} \equiv 1 \pmod m$.
证毕
欧拉定理可以推出费马小定理：
如果p是一个质数，而整数$a$不是$p$的倍数，
则有$a^{(p-1)} \equiv 1 \pmod p$。
例题
CF1114F
CF1114F Please, another Queries on Array?
线段树维护欧拉函数区间修改。
用一棵线段树维护区间积，因为有 $a_i,x\le 300$ ，所以可以选择开六十余棵线段树来维护质因数的出现情况，但这样必死无疑。所以选择压位，可以用 std::bitset 或者 long long 来状态压缩。