voidphi_table(){for (int i =1; i < maxn; i++) {phi[i] = i; }for (int i =2; i < maxn; i++) {if (phi[i] == i) {for (int j = i; j < maxn; j += i) {phi[j] =phi[j] / i * (i -1); } } }}
Pollard Rho 算法求欧拉函数
llget_phi(int n){ ll res =1;for (int i =2; i <=sqrt(n); i++) {if (n % i ==0) { n /= i; res *= i -1;while (n % i ==0) { n /= i; res *= i; } } }if (n >1) { res *= n -1; }return res;}