QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672790 | #998. 素数分解 | Qingyyx | AC ✓ | 10379ms | 3892kb | C++20 | 4.5kb | 2024-10-24 19:03:00 | 2024-10-24 19:03:02 |
Judging History
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 '