【数论】欧拉函数

ll eular(ll n) { ll ans = n; for(int i=2; i*i 1) ans = ans/n*(n-1); return ans; } 欧拉函数的一些性质： ① 当m,n互质时，有phi（m*n）= phi（m）*phi（n）； ② 若i%p==0，有phi（i*p） = p * phi(i)； ③ 对于互质x与p，有x^phi§≡1（mod p),因此x的逆元为x^(phi§-1)，即欧拉定理。 （特别地，当p为质数时，phi（p）=p-1,此时逆元为x^(p-2)，即费马小定理） ④ 当n为奇数时，phi(2n)=phi(n) ⑤ 若