Submission #1205800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205800		woohyun_jng	Hack (APIO25_hack)	C++20	100 / 100	80 ms	964 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX = 1'000'000'000;

signed hack() {
    int st = MAX / 2 + 1, en = MAX, md, V, X;
    vector<int> tmp, arr;

    while (st <= en) {
        md = st + en >> 1, tmp.clear();
        X = (int)sqrt(md - st + 1);
        for (int i = 1; i <= X; i++)
            tmp.push_back(i);
        for (int i = 1; st + i * X <= md; i++)
            tmp.push_back(st + i * X);
        tmp.push_back(md + 1);

        if (collisions(tmp) > 0)
            en = md - 1, V = md;
        else
            st = md + 1;
    }

    X = V;
    for (int i = 2; i * i <= V; i++) {
        if (X % i)
            continue;
        arr.push_back(i);
        while (X % i == 0)
            X /= i;
    }
    if (X > 1)
        arr.push_back(X);

    for (int i : arr) {
        while (V % i == 0 && collisions({1, V / i + 1}) > 0)
            V /= i;
    }

    return V;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 75 / 75