【数论】欧拉函数

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