bzoj4802: 欧拉函数

已知$n$，求$\phi (n)$ Miller-Rabin + Pollard-rho 对大整数进行质因数分解，然后直接计算欧拉函数。

#include <cmath> #include <cstdio> #include <vector> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; int T, CAP = 20; ll n; inline ll inc(ll a, ll b, ll mod) { a += b; return a >= mod ? a - mod : a; } inline ll dec(ll a, ll b, ll mod) { a -= b; return a < 0 ? a + mod : a; } inline ll mul(ll a, ll b, ll mod) { ll rst = 0; while (b) { if (b&1) rst = inc(rst, a, mod); b >>= 1, a = inc(a, a, mod); } return rst; } inline ll pow(ll a, ll b, ll mod) { ll rst = 1; while (b) { if (b&1) rst = mul(rst, a, mod); b >>= 1, a = mul(a, a, mod); } return rst; } ll gcd(ll a, ll b) { return a == 0 ? b : gcd(b%a, a); } inline ll range(ll l, ll r) { return l + rand() % (r - l + 1); } inline bool witness2(ll a, ll x) { ll m = x - 1, t = 0; while (! (m&1)) m>>=1, ++t; ll fac = pow(a, m, x), lst = fac; while (t--) { fac = mul(fac, fac, x); if (fac == 1 and lst != 1 and lst != x - 1) return true; lst = fac; } return lst != 1; } inline bool MillerRabin(ll x) { if (x < 2LL) return false; if (x == 2LL) return true; if (! (x&1LL)) return false; for (int i = 1; i <= CAP; i++) { ll a = range(2, x-1); if (witness2(a, x)) return false; } return true; } #define ABS(x) ((x) < 0 ? -(x) : (x)) inline ll PollardRho(ll x, ll a) { ll x1 = range(0, x - 1), x2 = x1; while(1) { x2 = inc(mul(x2, x2, x), a, x); x2 = inc(mul(x2, x2, x), a, x); ll d = gcd(ABS(x2 - x1), x); if (d != 1 and d != x) return d; x1 = inc(mul(x1, x1, x), a, x); if (x1 == x2) return x; } return x; } vector<ll> ls; void findFac(ll x) { if (MillerRabin(x)) return ls.push_back(x), void(0); ll p = x; while (p >= x) p = PollardRho(p, range(0, x - 1)); findFac(p), findFac(x / p); } int main() { srand(23333); cin >> n; if (n == 1) return puts("1"), 0; if (MillerRabin(n)) cout << n - 1 << endl; else { findFac(n); sort(ls.begin(), ls.end()); ls.erase(unique(ls.begin(), ls.end()), ls.end()); ll phi = n; for (vector<ll>::iterator i = ls.begin(); i != ls.end(); ++i) phi = (phi/(*i))*((*i)-1); cout << phi << endl; } return 0; }