QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#481043 | #998. 素数分解 | PYD1# | AC ✓ | 14645ms | 3936kb | C++14 | 2.8kb | 2024-07-16 20:11:31 | 2024-07-16 20:11:34 |
Judging History
answer
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <random>
#include <cstdio>
#include <time.h>
#include <stdio.h>
#include <iomanip>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
// typedef long long ll;
typedef unsigned long long ull;
typedef __int128 ll;
#define fi first
#define se second
#define mk make_pair
char buf[1 << 20],*p1 = buf,*p2 = buf;
inline char gc(){
if (p1 == p2) p1 = buf,p2 = buf + fread(buf,1,1 << 20,stdin);
if (p1 == p2) return EOF;
return *p1++;
// return getchar();
}
inline ll read(){
ll t = 0,f = 1;
register char c = gc();
while (c < 48 || c > 57){
if (c == EOF) exit(0);
f = (c == '-') ? (-1) : (f),c = gc();
}
while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = gc();
return f * t;
}
const int T = 12,P[T + 1] = {0,2,3,5,7,11,13,17,19,23,29,31,37},STP = 128;
mt19937 myrand((int)time(0));
inline ll rnd(ll l,ll r) {return myrand() % (r - l + 1) + l;}
inline ll abs(ll x) {return x >= 0 ? x : -x;}
ll mul(ll a,ll b,ll mod){
ll ans = 0;
a %= mod,b %= mod;
for (;b;a = a * 10000000 % mod,b /= 10000000) ans = (ans + a * (b % 10000000)) % mod;
return ans;
}
ll fap(ll a,ll p,ll mod){
ll ans = 1;a %= mod;
for (;p;p >>= 1,a = mul(a,a,mod)) if (p & 1) ans = mul(ans,a,mod);
return ans % mod;
}
bool miller_rabin(ll a,ll p,ll x,ll y){//p-1=2^x*y
a %= p;
ll cur = fap(a,y,p),lst = -1;
if (cur == 0) return 1;
for (int _ = 1;_ <= x;_++){
lst = cur,cur = mul(cur,cur,p);
if (cur == 1 && lst != 1 && lst != p - 1) return 0;
if (cur == 1) return 1;
}
return 0;
}
bool check(ll a){
if (a <= 2 || !(a & 1)) return a == 2;
ll x = 0,y = a - 1;
while (!(y & 1)) ++x,y >>= 1;
for (int i = 1;i <= T;i++) if (!miller_rabin(P[i],a,x,y)) return 0;
return 1;
}
inline ll f(ll x,ll c,ll mod) {return (mul(x,x,mod) + c) % mod;}
ll pollard_rho(ll n){
ll c = rnd(1,n - 1);
ll s = f(0,c,n),t = f(s,c,n);
while (s != t){
ll prod = 1;
for (int _ = 0;_ < STP;_++){
ll val = abs(s - t);
prod = mul(prod,val,n);
s = f(s,c,n),t = f(f(t,c,n),c,n);
if (prod == 0){
ll d = __gcd(val,n);
if (1 < d && d < n) return d;
break;
}
}
ll d = __gcd(prod,n);
if (1 < d && d < n) return d;
s = f(s,c,n),t = f(f(t,c,n),c,n);
}
return n;
}
void write(ll x){
if (x > 9) write(x / 10);
putchar((x % 10) ^ 48);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
#endif
ll n = read(),t = 0;
do{
t = pollard_rho(n);
}while (t == n);
ll a = t,b = n / t;
if (a > b) swap(a,b);
write(a),putchar(' '),write(b),putchar('\n');
// printf("%lld %lld\n",a,b);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
input:
9866369
output:
113 87313
result:
ok single line: '113 87313'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
9676411
output:
617 15683
result:
ok single line: '617 15683'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
9717809
output:
727 13367
result:
ok single line: '727 13367'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
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: 3628kb
input:
9561023
output:
1163 8221
result:
ok single line: '1163 8221'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
9545761
output:
1367 6983
result:
ok single line: '1367 6983'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
9607667
output:
1621 5927
result:
ok single line: '1621 5927'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
9597001
output:
2161 4441
result:
ok single line: '2161 4441'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
9761267
output:
3023 3229
result:
ok single line: '3023 3229'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
982258310053
output:
3947 248861999
result:
ok single line: '3947 248861999'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
951649112653
output:
60727 15670939
result:
ok single line: '60727 15670939'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
970510479737
output:
82361 11783617
result:
ok single line: '82361 11783617'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
986989368881
output:
104347 9458723
result:
ok single line: '104347 9458723'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
957993963593
output:
137957 6944149
result:
ok single line: '137957 6944149'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
994965772309
output:
189859 5240551
result:
ok single line: '189859 5240551'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
978534040373
output:
243157 4024289
result:
ok single line: '243157 4024289'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
971024997479
output:
316531 3067709
result:
ok single line: '316531 3067709'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
953600891731
output:
550909 1730959
result:
ok single line: '550909 1730959'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
957601483897
output:
974189 982973
result:
ok single line: '974189 982973'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
977141658538805467
output:
245593 3978703214419
result:
ok single line: '245593 3978703214419'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
993640296811069513
output:
15772423 62998582831
result:
ok single line: '15772423 62998582831'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
972033526800786343
output:
22838183 42561771521
result:
ok single line: '22838183 42561771521'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
954171962745034819
output:
35159623 27138287653
result:
ok single line: '35159623 27138287653'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
978341504612724647
output:
52896463 18495404969
result:
ok single line: '52896463 18495404969'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
964156325695679951
output:
82257599 11721182449
result:
ok single line: '82257599 11721182449'
Test #27:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
981810768141725077
output:
120632453 8138861009
result:
ok single line: '120632453 8138861009'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
996600025433706263
output:
188473367 5287749889
result:
ok single line: '188473367 5287749889'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
953178770133147331
output:
434148317 2195514143
result:
ok single line: '434148317 2195514143'
Test #30:
score: 0
Accepted
time: 3ms
memory: 3648kb
input:
979704186959920183
output:
965382697 1014835039
result:
ok single line: '965382697 1014835039'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
9681177706327259719477027
output:
30892241 313385413066253747
result:
ok single line: '30892241 313385413066253747'
Test #32:
score: 0
Accepted
time: 44ms
memory: 3764kb
input:
9940536208068119834895493
output:
9801019853 1014234881385881
result:
ok single line: '9801019853 1014234881385881'
Test #33:
score: 0
Accepted
time: 42ms
memory: 3936kb
input:
9997038881982298860346319
output:
17471050273 572205947883503
result:
ok single line: '17471050273 572205947883503'
Test #34:
score: 0
Accepted
time: 60ms
memory: 3856kb
input:
9756859113937123210682929
output:
30453215099 320388473999171
result:
ok single line: '30453215099 320388473999171'
Test #35:
score: 0
Accepted
time: 68ms
memory: 3764kb
input:
9990078255400923282753323
output:
54825911561 182214540004243
result:
ok single line: '54825911561 182214540004243'
Test #36:
score: 0
Accepted
time: 82ms
memory: 3704kb
input:
9883626478214751636971843
output:
99236894717 99596289327679
result:
ok single line: '99236894717 99596289327679'
Test #37:
score: 0
Accepted
time: 100ms
memory: 3928kb
input:
9573361345198621696137959
output:
174744513737 54784903631407
result:
ok single line: '174744513737 54784903631407'
Test #38:
score: 0
Accepted
time: 202ms
memory: 3684kb
input:
9625069927040072137408201
output:
315510198349 30506367075949
result:
ok single line: '315510198349 30506367075949'
Test #39:
score: 0
Accepted
time: 150ms
memory: 3624kb
input:
9558955213557944940797347
output:
961448896637 9942239516831
result:
ok single line: '961448896637 9942239516831'
Test #40:
score: 0
Accepted
time: 466ms
memory: 3700kb
input:
9840941836621191397321379
output:
3053341569527 3223007191477
result:
ok single line: '3053341569527 3223007191477'
Test #41:
score: 0
Accepted
time: 11ms
memory: 3860kb
input:
961656201462920497194293996611
output:
973825889 987503220365627902499
result:
ok single line: '973825889 987503220365627902499'
Test #42:
score: 0
Accepted
time: 98ms
memory: 3636kb
input:
996526819694097128105196470881
output:
994411349447 1002127359314908823
result:
ok single line: '994411349447 1002127359314908823'
Test #43:
score: 0
Accepted
time: 356ms
memory: 3928kb
input:
984638359916649895753226868473
output:
1913886315953 514470661976784841
result:
ok single line: '1913886315953 514470661976784841'
Test #44:
score: 0
Accepted
time: 1442ms
memory: 3700kb
input:
954594052218344282851704873817
output:
3979498549097 239877974684763761
result:
ok single line: '3979498549097 239877974684763761'
Test #45:
score: 0
Accepted
time: 2334ms
memory: 3700kb
input:
951130323482838313925006521277
output:
7557378146273 125854536464064349
result:
ok single line: '7557378146273 125854536464064349'
Test #46:
score: 0
Accepted
time: 662ms
memory: 3700kb
input:
962697697567853678189739826037
output:
15100422367399 63753031150060163
result:
ok single line: '15100422367399 63753031150060163'
Test #47:
score: 0
Accepted
time: 1980ms
memory: 3692kb
input:
956492846963172046572961978627
output:
30582959699219 31275352561367633
result:
ok single line: '30582959699219 31275352561367633'
Test #48:
score: 0
Accepted
time: 1668ms
memory: 3928kb
input:
990250331253981534128026179673
output:
61400770095961 16127653280347393
result:
ok single line: '61400770095961 16127653280347393'
Test #49:
score: 0
Accepted
time: 9942ms
memory: 3652kb
input:
963782379204510691122291047909
output:
244564652505673 3940808163935933
result:
ok single line: '244564652505673 3940808163935933'
Test #50:
score: 0
Accepted
time: 14645ms
memory: 3764kb
input:
955342769363561101863533963531
output:
973806882626147 981039245468473
result:
ok single line: '973806882626147 981039245468473'