QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481043#998. 素数分解PYD1#AC ✓14645ms3936kbC++142.8kb2024-07-16 20:11:312024-07-16 20:11:34

Judging History

This is the latest submission verdict.

  • [2024-07-16 20:11:34]
  • Judged
  • Verdict: AC
  • Time: 14645ms
  • Memory: 3936kb
  • [2024-07-16 20:11:31]
  • Submitted

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'