QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672790#998. 素数分解QingyyxAC ✓10379ms3892kbC++204.5kb2024-10-24 19:03:002024-10-24 19:03:02

Judging History

This is the latest submission verdict.

  • [2024-10-24 19:03:02]
  • Judged
  • Verdict: AC
  • Time: 10379ms
  • Memory: 3892kb
  • [2024-10-24 19:03:00]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll __int128_t
#define lll __int128_t
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
// #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline int indi(char* s) { int n = 0; for (s[0] = gc(); !isdigit(s[0]); s[0] = gc()); for (; isdigit(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(auto* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int n, m, q;
ll abs(ll x) { return x > 0 ? x : -x; }

void write(lll x) {
    static int oc[100], top; top = 0;
    while (x) {
        oc[++top] = x % 10;
        x /= 10;
    }
    while (top) {
        putchar(oc[top--] + '0');
    }
    putchar(' ');
}
template<class T = lll>
T randint(T l, T r = 0) {
    static mt19937_64 eng(time(0));
    if (l > r) swap(l, r);
    // uniform_int_distribution<long long> dis(l, r);
    // return dis(eng);
    ll d = r - l + 1;
    ll v = ((ll)eng() << 64) + eng();
    v = abs(v);
    // printf("l = "); write(l); enl;
    // printf("r = "); write(r); enl;
    // printf("res = "); write(v % d + l); enl;
    // system("pause");
    return v % d + l;
}
ll qpow(ll a, ll n, ll p) {
    ll res = 1;
    while (n) {
        if (n & 1)
            res = (lll)res * a % p;
        a = (lll)a * a % p;
        n >>= 1;
    }
    return res;
}
bool isPrime(ll x) {
    if (x < 3)return x == 2;
    if (x % 2 == 0)return false;
    ll A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
    while (d % 2 == 0)
        d /= 2, ++r;
    for (auto a : A) {
        ll v = qpow(a, d, x);
        if (v <= 1 || v == x - 1)continue;
        for (int i = 0; i < r; ++i) {
            v = (__int128)v * v % x;
            if (v == x - 1 && i != r - 1) {
                v = 1;
                break;
            }
            if (v == 1)return false;
        }
        if (v != 1)return false;
    }
    return true;
}
inline ll mul(ll x, ll y, ll p) {
    ll r = (__float128)x / p * y;
    ll res = x * y - r * p;
    return (res + p) % p;
    // ll res = 0;
    // while (y) {
    //     if (y & 1) res = (res + x) % p;
    //     x = (x + x) % p;
    //     y >>= 1;
    // }
    // return res;
}

ll Pollard_Rho(ll N) {
    if (N == 1)return 1;
    if (N == 4)return 2;
    // if (isPrime(N))return 1;
    while (true) {
        ll c = randint<>((ll)1, N - 1);
        auto f = [=](ll x) {return (mul(x, x, N) + c) % N; };

        ll t = 0, r = 0, p = 1, q;
        do {
            for (int i = 0; i < 128; ++i) {
                t = f(t), r = f(f(r));
                if (t == r || (q = mul(p, abs(t - r), N) % N) == 0)break;
                p = q;
            }
            ll d = __gcd(p, N);
            if (d > 1)return d;
        } while (t != r);
    }
}
map<ll, ll>um;
ll max_prime_factor(ll x) {
    if (um.count(x))return um[x];
    ll fac = Pollard_Rho(x);
    if (fac == 1)um[x] = x;
    else um[x] = max(max_prime_factor(fac), max_prime_factor(x / fac));
    return um[x];
}

void solve() {
    lll n = read<lll>();
    // write(n);
    lll ans = Pollard_Rho(n);
    lll ans2 = n / ans;
    if (ans > ans2) swap(ans, ans2);
    write(ans), write(n / ans);
}
signed main(signed argc, char const* argv[]) {
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //=============================================================

    int TxT = 1;
    while (TxT--)
        solve();
    //=============================================================
#ifdef LOCAL
    end :
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

input:

9866369

output:

113 87313 

result:

ok single line: '113 87313 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

9676411

output:

617 15683 

result:

ok single line: '617 15683 '

Test #3:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

9717809

output:

727 13367 

result:

ok single line: '727 13367 '

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

9957119

output:

829 12011 

result:

ok single line: '829 12011 '

Test #5:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

9868337

output:

983 10039 

result:

ok single line: '983 10039 '

Test #6:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

9561023

output:

1163 8221 

result:

ok single line: '1163 8221 '

Test #7:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

9545761

output:

1367 6983 

result:

ok single line: '1367 6983 '

Test #8:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

9607667

output:

1621 5927 

result:

ok single line: '1621 5927 '

Test #9:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

9597001

output:

2161 4441 

result:

ok single line: '2161 4441 '

Test #10:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

9761267

output:

3023 3229 

result:

ok single line: '3023 3229 '

Test #11:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

982258310053

output:

3947 248861999 

result:

ok single line: '3947 248861999 '

Test #12:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

951649112653

output:

60727 15670939 

result:

ok single line: '60727 15670939 '

Test #13:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

970510479737

output:

82361 11783617 

result:

ok single line: '82361 11783617 '

Test #14:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

986989368881

output:

104347 9458723 

result:

ok single line: '104347 9458723 '

Test #15:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

957993963593

output:

137957 6944149 

result:

ok single line: '137957 6944149 '

Test #16:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

994965772309

output:

189859 5240551 

result:

ok single line: '189859 5240551 '

Test #17:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

978534040373

output:

243157 4024289 

result:

ok single line: '243157 4024289 '

Test #18:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

971024997479

output:

316531 3067709 

result:

ok single line: '316531 3067709 '

Test #19:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

953600891731

output:

550909 1730959 

result:

ok single line: '550909 1730959 '

Test #20:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

957601483897

output:

974189 982973 

result:

ok single line: '974189 982973 '

Test #21:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

977141658538805467

output:

245593 3978703214419 

result:

ok single line: '245593 3978703214419 '

Test #22:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

993640296811069513

output:

15772423 62998582831 

result:

ok single line: '15772423 62998582831 '

Test #23:

score: 0
Accepted
time: 3ms
memory: 3620kb

input:

972033526800786343

output:

22838183 42561771521 

result:

ok single line: '22838183 42561771521 '

Test #24:

score: 0
Accepted
time: 3ms
memory: 3776kb

input:

954171962745034819

output:

35159623 27138287653 

result:

ok single line: '35159623 27138287653 '

Test #25:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

978341504612724647

output:

52896463 18495404969 

result:

ok single line: '52896463 18495404969 '

Test #26:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

964156325695679951

output:

82257599 11721182449 

result:

ok single line: '82257599 11721182449 '

Test #27:

score: 0
Accepted
time: 3ms
memory: 3628kb

input:

981810768141725077

output:

120632453 8138861009 

result:

ok single line: '120632453 8138861009 '

Test #28:

score: 0
Accepted
time: 7ms
memory: 3776kb

input:

996600025433706263

output:

188473367 5287749889 

result:

ok single line: '188473367 5287749889 '

Test #29:

score: 0
Accepted
time: 9ms
memory: 3856kb

input:

953178770133147331

output:

434148317 2195514143 

result:

ok single line: '434148317 2195514143 '

Test #30:

score: 0
Accepted
time: 13ms
memory: 3776kb

input:

979704186959920183

output:

965382697 1014835039 

result:

ok single line: '965382697 1014835039 '

Test #31:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

9681177706327259719477027

output:

30892241 313385413066253747 

result:

ok single line: '30892241 313385413066253747 '

Test #32:

score: 0
Accepted
time: 78ms
memory: 3768kb

input:

9940536208068119834895493

output:

9801019853 1014234881385881 

result:

ok single line: '9801019853 1014234881385881 '

Test #33:

score: 0
Accepted
time: 39ms
memory: 3636kb

input:

9997038881982298860346319

output:

17471050273 572205947883503 

result:

ok single line: '17471050273 572205947883503 '

Test #34:

score: 0
Accepted
time: 162ms
memory: 3712kb

input:

9756859113937123210682929

output:

30453215099 320388473999171 

result:

ok single line: '30453215099 320388473999171 '

Test #35:

score: 0
Accepted
time: 27ms
memory: 3640kb

input:

9990078255400923282753323

output:

54825911561 182214540004243 

result:

ok single line: '54825911561 182214540004243 '

Test #36:

score: 0
Accepted
time: 129ms
memory: 3584kb

input:

9883626478214751636971843

output:

99236894717 99596289327679 

result:

ok single line: '99236894717 99596289327679 '

Test #37:

score: 0
Accepted
time: 155ms
memory: 3644kb

input:

9573361345198621696137959

output:

174744513737 54784903631407 

result:

ok single line: '174744513737 54784903631407 '

Test #38:

score: 0
Accepted
time: 525ms
memory: 3652kb

input:

9625069927040072137408201

output:

315510198349 30506367075949 

result:

ok single line: '315510198349 30506367075949 '

Test #39:

score: 0
Accepted
time: 464ms
memory: 3640kb

input:

9558955213557944940797347

output:

961448896637 9942239516831 

result:

ok single line: '961448896637 9942239516831 '

Test #40:

score: 0
Accepted
time: 366ms
memory: 3644kb

input:

9840941836621191397321379

output:

3053341569527 3223007191477 

result:

ok single line: '3053341569527 3223007191477 '

Test #41:

score: 0
Accepted
time: 10ms
memory: 3600kb

input:

961656201462920497194293996611

output:

973825889 987503220365627902499 

result:

ok single line: '973825889 987503220365627902499 '

Test #42:

score: 0
Accepted
time: 381ms
memory: 3568kb

input:

996526819694097128105196470881

output:

994411349447 1002127359314908823 

result:

ok single line: '994411349447 1002127359314908823 '

Test #43:

score: 0
Accepted
time: 838ms
memory: 3596kb

input:

984638359916649895753226868473

output:

1913886315953 514470661976784841 

result:

ok single line: '1913886315953 514470661976784841 '

Test #44:

score: 0
Accepted
time: 434ms
memory: 3640kb

input:

954594052218344282851704873817

output:

3979498549097 239877974684763761 

result:

ok single line: '3979498549097 239877974684763761 '

Test #45:

score: 0
Accepted
time: 465ms
memory: 3564kb

input:

951130323482838313925006521277

output:

7557378146273 125854536464064349 

result:

ok single line: '7557378146273 125854536464064349 '

Test #46:

score: 0
Accepted
time: 1607ms
memory: 3644kb

input:

962697697567853678189739826037

output:

15100422367399 63753031150060163 

result:

ok single line: '15100422367399 63753031150060163 '

Test #47:

score: 0
Accepted
time: 2448ms
memory: 3708kb

input:

956492846963172046572961978627

output:

30582959699219 31275352561367633 

result:

ok single line: '30582959699219 31275352561367633 '

Test #48:

score: 0
Accepted
time: 6694ms
memory: 3892kb

input:

990250331253981534128026179673

output:

61400770095961 16127653280347393 

result:

ok single line: '61400770095961 16127653280347393 '

Test #49:

score: 0
Accepted
time: 10379ms
memory: 3772kb

input:

963782379204510691122291047909

output:

244564652505673 3940808163935933 

result:

ok single line: '244564652505673 3940808163935933 '

Test #50:

score: 0
Accepted
time: 3164ms
memory: 3684kb

input:

955342769363561101863533963531

output:

973806882626147 981039245468473 

result:

ok single line: '973806882626147 981039245468473 '