Submission #1214878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214878		anfi	Hack (APIO25_hack)	C++20	0 / 100	2 ms	956 KiB

hack

#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <iostream>
#include "hack.h"

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

vector<ll> get_all_divisors(ll x) {
    vector<ll> divisors;
    if (x == 0) return divisors;
    ll sqrt_x = sqrt(x);
    for (ll i = 1; i <= sqrt_x; i++) {
        if (x % i == 0) {
            divisors.push_back(i);
            if (i != x / i) {
                divisors.push_back(x / i);
            }
        }
    }
    return divisors;
}

vector<ll> get_divisors_in_range(ll x, ll low_bound, ll high_bound) {
    vector<ll> res;
    if (x == 0) return res;
    ll sqrt_x = sqrt(x);
    for (ll i = 1; i <= sqrt_x; i++) {
        if (x % i == 0) {
            if (i >= low_bound && i <= high_bound) {
                res.push_back(i);
            }
            ll j = x / i;
            if (j != i) {
                if (j >= low_bound && j <= high_bound) {
                    res.push_back(j);
                }
            }
        }
    }
    return res;
}

int hack() {
    const ll M_val = 1000000007;
    const int k_val = 40000;

    vector<ll> v1;
    for (int i = 1; i <= k_val; i++) {
        v1.push_back(i * M_val);
    }
    ll col1 = collisions(v1);

    if (col1 == 0) {
        ll low = 40001, high = 1000000000;
        while (low <= high) {
            ll mid = (low + high) / 2;
            vector<ll> test_vec = {1, 1 + mid};
            if (collisions(test_vec) == 1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    set<ll> candidates_T;
    for (int L = 1; L <= k_val; L++) {
        ll numerator = (ll)L * k_val - col1;
        if (numerator <= 0) break;
        ll denominator = (ll)L * (L + 1);
        if (numerator * 2 % denominator != 0) continue;
        ll T0 = (numerator * 2) / denominator;
        if (T0 == 0) continue;

        if (k_val - 1 < T0) {
            if (L == 0) {
                candidates_T.insert(T0);
            }
        } else {
            ll L0 = (k_val - 1) / T0;
            if (L0 == L) {
                candidates_T.insert(T0);
            }
        }
    }

    static vector<ll> divisors_M;
    if (divisors_M.empty()) {
        divisors_M = get_all_divisors(M_val);
    }

    vector<ll> candidate_list;
    for (ll T0 : candidates_T) {
        for (ll g : divisors_M) {
            if (M_val % g != 0) continue;
            ll M_div_g = M_val / g;
            if (gcd(T0, M_div_g) != 1) continue;
            ll candidate_n = g * T0;
            if (candidate_n > (ll)1e18) continue;
            candidate_list.push_back(candidate_n);
        }
    }

    vector<ll> passed_candidates;
    for (ll cn : candidate_list) {
        vector<ll> test_vec = {1, 1 + cn};
        if (collisions(test_vec) == 1) {
            passed_candidates.push_back(cn);
        }
    }

    if (passed_candidates.empty()) {
        ll low = 2, high = 1000000000;
        while (low <= high) {
            ll mid = (low + high) / 2;
            vector<ll> test_vec = {1, 1 + mid};
            if (collisions(test_vec) == 1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    ll G_val = passed_candidates[0];
    for (int i = 1; i < passed_candidates.size(); i++) {
        G_val = gcd(G_val, passed_candidates[i]);
    }

    vector<ll> divisors_G = get_divisors_in_range(G_val, 2, min(G_val, (ll)1000000000));

    ll best_candidate = -1;
    for (ll d : divisors_G) {
        ll g_d = gcd(d, M_val);
        ll T_d = d / g_d;
        ll q = k_val / T_d;
        ll r = k_val % T_d;
        ll term1 = T_d * (q * (q - 1) / 2);
        ll term2 = r * q;
        ll expected_col = term1 + term2;
        if (expected_col != col1) continue;

        vector<ll> test_vec = {1, 1 + d};
        if (collisions(test_vec) != 1) continue;

        if (d > best_candidate) {
            best_candidate = d;
        }
    }

    if (best_candidate == -1) {
        ll low = 2, high = 1000000000;
        while (low <= high) {
            ll mid = (low + high) / 2;
            vector<ll> test_vec = {1, 1 + mid};
            if (collisions(test_vec) == 1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        best_candidate = low;
    }

    return best_candidate;
}

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