Untitled
unknown
plain_text
22 days ago
2.0 kB
2
Indexable
Never
//--this-template-is-from-cp-algorithms------- #include <bits/stdc++.h> using namespace std; #define nl '\n' #define fi first #define se second typedef long long ll; using u64 = uint64_t; using u128 = __uint128_t; long long mult(ll a, ll b, ll mod) { return (__int128)a * b % mod; } long long f(ll x, ll c, ll mod) { return (mult(x, x, mod) + c) % mod; } u64 binpower(u64 base, u64 e, u64 mod) { u64 result = 1; base %= mod; while (e) { if (e & 1) result = (u128)result * base % mod; base = (u128)base * base % mod; e >>= 1; } return result; } bool check_composite(u64 n, u64 a, u64 d, int s) { u64 x = binpower(a, d, n); if (x == 1 || x == n - 1) return false; for (int r = 1; r < s; r++) { x = (u128)x * x % n; if (x == n - 1) return false; } return true; }; bool MillerRabin(u64 n) { // returns true if n is prime, else returns false. if (n < 2) return false; int r = 0; u64 d = n - 1; while ((d & 1) == 0) { d >>= 1; r++; } for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n == a) return true; if (check_composite(n, a, d, r)) return false; } return true; } ll rho(ll n) { if(MillerRabin(n)) return n; if(n == 1) return 1; if(n % 2 == 0) return 2; srand(time(NULL)); ll x = (rand() % (n - 2)) + 2; ll y = x; ll c = (rand() % (n - 1)) + 1; ll g = 1; while (g == 1) { x = f(x, c, n); y = f(y, c, n); y = f(y, c, n); g = __gcd(abs(x - y), n); if(g == n) rho(n); } if(MillerRabin(g)) return g; else return rho(g); } void Solve(){ ll n; cin>>n; vector<ll> res; while(n > 1){ ll k = rho(n); res.push_back(k); n /= k; } sort(res.begin(), res.end()); for(auto x: res) cout<<x<<nl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Solve(); }
Leave a Comment