QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88854#5003. Etched Emerald OrbsSorahISAAC ✓35ms7220kbC++203.5kb2023-03-17 19:41:282023-03-17 19:41:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-17 19:41:37]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:7220kb
  • [2023-03-17 19:41:28]
  • 提交

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'