Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define sz(x) ((int)x.size ())
- #define all(x) (x).begin(), (x).end()
- #define re return
- typedef long long ll;
- typedef vector <ll> vll;
- const ll inf = 1e10 + 7;
- ll n;
- ll mul (ll x, ll y, ll mod) {
- ll ans = 0;
- while (y) {
- if (y & 1) ans = (ans + x) % mod;
- x = (x + x) % mod;
- y >>= 1;
- }
- re ans;
- }
- ll power (ll x, ll p, ll mod) {
- ll ans = 1 % mod;
- while (p) {
- if (p & 1) ans = mul (ans, x, mod);
- x = mul (x, x, mod);
- p /= 2;
- }
- re ans;
- }
- ll myrand() {
- ll a = rand() + (rand() << 15);
- re rand() + (rand() << 15) + (a << 30);
- }
- bool get (ll s, ll d, ll n) {
- ll a = 1 + myrand() % (n - 1);
- if (power (a, n - 1, n) != 1) re false;
- a = power (a, d, n);
- if (a == 1) re true;
- for (int i = 0; i < s; i++) {
- if (a == n - 1) re true;
- a = mul (a, a, n);
- }
- re false;
- }
- bool is_prime (ll n) {
- ll s = 0, d = n - 1;
- while (d % 2 == 0) { s++; d /= 2; }
- for (int i = 0; i < 10; i++)
- if (!get (s, d, n)) re false;
- re true;
- }
- ll func (ll x, ll n) {
- re (mul (x, x, n) + 1) % n;
- }
- void go (ll n, vll& ans) {
- if (n < inf) {
- for (ll j = 2; j * j <= n; j++)
- while (n % j == 0) {
- ans.pb(j);
- n /= j;
- }
- if (n > 1) ans.pb(n);
- re;
- }
- if (is_prime(n)) { ans.pb(n); re; }
- ll x = 1 + rand() % (n - 1);
- ll y = x;
- ll d = 1;
- while (d == 1) {
- x = func (x, n);
- y = func (func (y, n), n);
- d = (n + y - x) % n;
- d = __gcd(d, n);
- }
- go (d, ans);
- go (n / d, ans);
- }
- vll fact (ll n) {
- vll ans;
- go (n, ans);
- // sort (all(ans));
- re ans;
- }
- int main() {
- srand(time(0));
- cin >> n;
- auto ans = fact (n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement