QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88854 | #5003. Etched Emerald Orbs | SorahISA | AC ✓ | 35ms | 7220kb | C++20 | 3.5kb | 2023-03-17 19:41:28 | 2023-03-17 19:41:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int __int128
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define ALL(x) begin(x), end(x)
#define SZ(x) ((int)(x).size())
#define eb emplace_back
#define ee emplace
template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}
int mul(int a, int b, int n) {
return a * b % n;
}
bool Miller_Rabin(int a, int n) {
if((a = a % n) == 0) return 1;
if(n % 2 == 0) return n == 2;
int tmp = (n - 1) / ((n - 1) & (1 - n));
int t = __lg((int64_t)((n - 1) & (1 - n))), x = 1;
for( ; tmp; tmp >>= 1, a = mul(a, a, n))
if(tmp & 1) x = mul(x, a, n);
if(x == 1 || x == n - 1) return 1;
while(--t)
if((x = mul(x, x, n)) == n - 1) return 1;
return 0;
}
bool prime(int x) {
const static int chks[7] = {
2, 325, 9375, 28178, 450775, 9780504, 1795265022,
};
for(int i = 0; i < 7; ++i){
if(!Miller_Rabin(chks[i], x)) return false;
}
return true;
}
void PollardRho(int n, map<int, int> &cnt) {
if(n == 1) return;
if(prime(n)) return ++cnt[n], void();
if(n % 2 == 0) return PollardRho(n/2, cnt), ++cnt[2], void();
int x = 2, y = 2, d = 1, p = 1;
#define f(x, n, p) ((mul(x, x, n) + p) % n)
while(true) {
// cerr << "! " << "pollarg rho while(true)" << "\n";
if(d != n && d != 1) {
PollardRho(n/d, cnt);
PollardRho(d, cnt);
return;
}
if(d == n) ++p;
x = f(x, n, p), y = f(f(y, n, p), n, p);
d = __gcd((int64_t)abs((int64_t)x - (int64_t)y), (int64_t)n);
}
#undef f
}
void print(int x) {
string s;
while (x) s += (char)((x % 10) + '0'), x /= 10;
reverse(ALL(s));
cout << s;
}
void dfs(vector<int> &fact, vector<pii> &pfact, int val, int now) {
if (now == SZ(pfact)) return;
for (int i = 0; i <= pfact[now].second; ++i) {
fact.eb(val);
dfs(fact, pfact, val, now+1);
val *= pfact[now].first;
}
}
int max_fact_k_square(int k) {
map<int, int> cnt;
PollardRho(k, cnt);
vector<int> fact{1};
vector<pii> pfact(ALL(cnt));
dfs(fact, pfact, 1, 0);
sort(ALL(fact));
int ans = 1;
for (int f : fact) {
auto it = lower_bound(ALL(fact), k / f);
if (it != begin(fact)) {
int x = *prev(it);
chmax(ans, f * x);
}
}
return ans;
}
void solve() {
int64_t _k; cin >> _k;
int k = _k, f, x, y;
if(k & 1) {
map<int, int> cnt;
PollardRho(k, cnt);
f = max_fact_k_square(k);
// print(f);
x = (k + f) / 2, y = k * k / f / 2 + k / 2 + 1;
}
else {
map<int, int> cnt;
PollardRho(k/2, cnt);
f = max_fact_k_square(k / 2);
// print(f);
// cout << endl;
x = (k/2) + f, y = (k/2) * (k/2) / f + k/2;
}
print(x);
cout << " ";
print(y);
cout << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; ++i) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3408kb
input:
5
output:
3 15
result:
ok single line: '3 15'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
7
output:
4 28
result:
ok single line: '4 28'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3312kb
input:
2625
output:
2415 2875
result:
ok single line: '2415 2875'
Test #4:
score: 0
Accepted
time: 4ms
memory: 3312kb
input:
3874168794131721959
output:
3744304003028637896 4013365524702817208
result:
ok single line: '3744304003028637896 4013365524702817208'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
2564440520291015625
output:
2559273647539021875 2569628297865234375
result:
ok single line: '2559273647539021875 2569628297865234375'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3280kb
input:
3920781456123456907
output:
2005087667647282542 87942380598179860122
result:
ok single line: '2005087667647282542 87942380598179860122'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
3821233887414018075
output:
3821141424039289350 3821326355263683266
result:
ok single line: '3821141424039289350 3821326355263683266'
Test #8:
score: 0
Accepted
time: 5ms
memory: 3572kb
input:
3202261912080000000
output:
3202124306040000000 3202399529947296000
result:
ok single line: '3202124306040000000 3202399529947296000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
4000000000000000000
output:
3953125000000000000 4048000000000000000
result:
ok single line: '3953125000000000000 4048000000000000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3280kb
input:
3850964497573793568
output:
3843850920814152616 3858104452461399792
result:
ok single line: '3843850920814152616 3858104452461399792'
Test #11:
score: 0
Accepted
time: 34ms
memory: 3300kb
input:
3000000048000000189
output:
3000000045000000168 3000000051000000216
result:
ok single line: '3000000045000000168 3000000051000000216'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3304kb
input:
3940856337148318715
output:
2364513802288991229 11822569011444956145
result:
ok single line: '2364513802288991229 11822569011444956145'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
3429027972617882818
output:
1714513986308941410 2939558209248976930980051328503846690
result:
ok single line: '1714513986308941410 2939558209248976930980051328503846690'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3712195277197288159
output:
1856097638598644080 6890196888022925538423383990439448720
result:
ok single line: '1856097638598644080 6890196888022925538423383990439448720'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
3919508164532054904
output:
3905150937354775728 3933971349510016656
result:
ok single line: '3905150937354775728 3933971349510016656'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
3756195324343219283
output:
3742436314964993406 3770055876613765962
result:
ok single line: '3742436314964993406 3770055876613765962'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
3802882314465069179
output:
3745383883838969855 3862173680130180695
result:
ok single line: '3745383883838969855 3862173680130180695'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3292kb
input:
3042689028198105137
output:
2970337847529485654 3118652850293963138
result:
ok single line: '2970337847529485654 3118652850293963138'
Test #19:
score: 0
Accepted
time: 22ms
memory: 7092kb
input:
3895719049963540800
output:
3895718446006710400 3895719653920558464
result:
ok single line: '3895718446006710400 3895719653920558464'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
3698458423184683311
output:
3225606430876782069 4333757892460993217
result:
ok single line: '3225606430876782069 4333757892460993217'
Test #21:
score: 0
Accepted
time: 35ms
memory: 3436kb
input:
3257555856309165270
output:
3063381900702289660 3478011298484813844
result:
ok single line: '3063381900702289660 3478011298484813844'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
3177350279531944282
output:
1710880919747969998 22241451956723609974
result:
ok single line: '1710880919747969998 22241451956723609974'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3372kb
input:
3269210676502105169
output:
1645575843876898575 245190800737657887675
result:
ok single line: '1645575843876898575 245190800737657887675'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3276kb
input:
3491285480940446877
output:
2327523653960297918 6982570961880893754
result:
ok single line: '2327523653960297918 6982570961880893754'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3364kb
input:
3287336280107990913
output:
3170271203063752656 3413378302499341872
result:
ok single line: '3170271203063752656 3413378302499341872'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3324kb
input:
3497242929917413346
output:
2274826852734331322 7559426710871800394
result:
ok single line: '2274826852734331322 7559426710871800394'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
3965761515553888606
output:
2007980514204500560 158630460622155544240
result:
ok single line: '2007980514204500560 158630460622155544240'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
3941379233488642363
output:
2149843218266532198 23648275400931854178
result:
ok single line: '2149843218266532198 23648275400931854178'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
3048271717791871289
output:
1532556499000333079 277392726319060287299
result:
ok single line: '1532556499000333079 277392726319060287299'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
3360919089269334657
output:
2240612726179556438 6721838178538669314
result:
ok single line: '2240612726179556438 6721838178538669314'
Test #31:
score: 0
Accepted
time: 4ms
memory: 3356kb
input:
3005969580964965071
output:
1564965857732939174 37949005819670702402
result:
ok single line: '1564965857732939174 37949005819670702402'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3300kb
input:
3214168257188113442
output:
2329534791906981302 5182026373833897182
result:
ok single line: '2329534791906981302 5182026373833897182'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
3716821287908134630
output:
3185846818206972540 4460185545489761556
result:
ok single line: '3185846818206972540 4460185545489761556'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
3959018189256590546
output:
1998440027817505944 208966466185015346472
result:
ok single line: '1998440027817505944 208966466185015346472'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3360kb
input:
3867241015987051975
output:
3259050051977660500 4754508487971959500
result:
ok single line: '3259050051977660500 4754508487971959500'
Test #36:
score: 0
Accepted
time: 3ms
memory: 3432kb
input:
3515568968773730009
output:
1840619347337996265 39058580109219850185
result:
ok single line: '1840619347337996265 39058580109219850185'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
3849970182511318969
output:
2266684044334211125 12769524028735820125
result:
ok single line: '2266684044334211125 12769524028735820125'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
3289075253438216117
output:
1644582142259987768 60755798081510728113224
result:
ok single line: '1644582142259987768 60755798081510728113224'
Test #39:
score: 0
Accepted
time: 17ms
memory: 3276kb
input:
3549463895942506999
output:
1803153067056106804 112596317746414385644
result:
ok single line: '1803153067056106804 112596317746414385644'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
3519536436932095244
output:
2639652327699071433 5279304655398142866
result:
ok single line: '2639652327699071433 5279304655398142866'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3912360022899723581
output:
1956360155110553370 21244114924345499044830
result:
ok single line: '1956360155110553370 21244114924345499044830'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
3294876212711547573
output:
2957605419284381286 3718969190585311122
result:
ok single line: '2957605419284381286 3718969190585311122'
Test #43:
score: 0
Accepted
time: 17ms
memory: 3376kb
input:
3830724478173758402
output:
3053142001576633610 5139723075750063290
result:
ok single line: '3053142001576633610 5139723075750063290'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3308kb
input:
3210282295698275701
output:
2582864835023285695 4240321350923768755
result:
ok single line: '2582864835023285695 4240321350923768755'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
3171629758012311933
output:
2879503618245093240 3529720514264868360
result:
ok single line: '2879503618245093240 3529720514264868360'
Test #46:
score: 0
Accepted
time: 7ms
memory: 3360kb
input:
3890188847299078027
output:
2121921189435860742 23341133083794468162
result:
ok single line: '2121921189435860742 23341133083794468162'
Test #47:
score: 0
Accepted
time: 3ms
memory: 3304kb
input:
3063016398207028265
output:
1837809838924216959 9189049194621084795
result:
ok single line: '1837809838924216959 9189049194621084795'
Test #48:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
3010223201362255716
output:
2508519334468546430 3762779001702819645
result:
ok single line: '2508519334468546430 3762779001702819645'
Test #49:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
3597834333906208856
output:
3486515202287823681 3716496416159052156
result:
ok single line: '3486515202287823681 3716496416159052156'
Test #50:
score: 0
Accepted
time: 0ms
memory: 3328kb
input:
3152900099831435122
output:
1697715438370772758 22070300698820045854
result:
ok single line: '1697715438370772758 22070300698820045854'
Test #51:
score: 0
Accepted
time: 1ms
memory: 3300kb
input:
3762123640637182797
output:
2508082427091455198 7524247281274365594
result:
ok single line: '2508082427091455198 7524247281274365594'
Test #52:
score: 0
Accepted
time: 0ms
memory: 3276kb
input:
3927484292243435684
output:
3782584133885895014 4083928089923845679
result:
ok single line: '3782584133885895014 4083928089923845679'
Test #53:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
3676544907277140992
output:
3665773779619102493 3687379518988173824
result:
ok single line: '3665773779619102493 3687379518988173824'
Test #54:
score: 0
Accepted
time: 0ms
memory: 3292kb
input:
3401658549814387546
output:
1700829274907193774 2892820222381330531141651420677169302
result:
ok single line: '1700829274907193774 2892820222381330531141651420677169302'
Test #55:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3460941698564515033
output:
2850187281170777086 4404834889082110042
result:
ok single line: '2850187281170777086 4404834889082110042'
Test #56:
score: 0
Accepted
time: 3ms
memory: 3360kb
input:
3763269160521556304
output:
2822451870391167228 5644903740782334456
result:
ok single line: '2822451870391167228 5644903740782334456'
Test #57:
score: 0
Accepted
time: 1ms
memory: 3292kb
input:
3332740651914069784
output:
2499555488935552338 4999110977871104676
result:
ok single line: '2499555488935552338 4999110977871104676'
Test #58:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
3335651979228443499
output:
3203546950348109103 3479120881560849671
result:
ok single line: '3203546950348109103 3479120881560849671'
Test #59:
score: 0
Accepted
time: 3ms
memory: 3356kb
input:
3936715707987254627
output:
3203980260769393994 5103970011989647358
result:
ok single line: '3203980260769393994 5103970011989647358'
Test #60:
score: 0
Accepted
time: 15ms
memory: 3308kb
input:
3335998934730949722
output:
2693266047254129688 4381656849461807784
result:
ok single line: '2693266047254129688 4381656849461807784'
Test #61:
score: 0
Accepted
time: 2ms
memory: 3304kb
input:
3857260769985676583
output:
1928630384992838292 7439230323835247297442281875130116236
result:
ok single line: '1928630384992838292 7439230323835247297442281875130116236'
Test #62:
score: 0
Accepted
time: 1ms
memory: 3372kb
input:
3998787182358573719
output:
3185017725080449464 5371098517001972424
result:
ok single line: '3185017725080449464 5371098517001972424'
Test #63:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
3435841181648576365
output:
2952900408826454947 4107636692543525695
result:
ok single line: '2952900408826454947 4107636692543525695'
Test #64:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
3067673414307760850
output:
2994349824881957450 3144678140657994650
result:
ok single line: '2994349824881957450 3144678140657994650'
Test #65:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
3194568006647411792
output:
3193165650191464728 3195971595402529284
result:
ok single line: '3193165650191464728 3195971595402529284'
Test #66:
score: 0
Accepted
time: 0ms
memory: 3304kb
input:
3943941543572485437
output:
3931375682447924319 3956587990830592803
result:
ok single line: '3931375682447924319 3956587990830592803'
Test #67:
score: 0
Accepted
time: 4ms
memory: 3304kb
input:
3662022291702274748
output:
2746516718776706061 5493033437553412122
result:
ok single line: '2746516718776706061 5493033437553412122'
Test #68:
score: 0
Accepted
time: 2ms
memory: 3324kb
input:
3089001499754721531
output:
2059334333169814354 6178002999509443062
result:
ok single line: '2059334333169814354 6178002999509443062'
Test #69:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
3859496316748877632
output:
2894622237561658224 5789244475123316448
result:
ok single line: '2894622237561658224 5789244475123316448'
Test #70:
score: 0
Accepted
time: 28ms
memory: 7220kb
input:
3139862719600807200
output:
3139861397158005520 3139864042044722850
result:
ok single line: '3139861397158005520 3139864042044722850'