提出 #17138768

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <utility>
using i64 = long long;

auto get_prime_factor(i64 n) {
    std::vector<i64> ret;
    for (i64 i = 2; i * i <= n; i++) {
        if (n % i) continue;
        i64 t = 1;
        while (n % i == 0) {
            n /= i;
            t *= i;
        }
        ret.push_back(t);
    }

    if (n > 1) ret.push_back(n);

    return ret;
}

std::pair<i64, i64> extgcd(const i64 a, const i64 b) {
    if (!b) return { 1ll, 0ll };
    const auto [y, x] = extgcd(b, a % b);
    return { x, y - a / b * x };
}

int main() {
    i64 n;
    std::cin >> n;

    const auto ps = get_prime_factor(2 * n);

    if (ps.size() == 1) {
        std::cout << 2 * n - 1 << std::endl;
        return 0;
    }

    i64 ret = 2 * n;
    const i64 m = ps.size();
    for (int i = 1; i + 1 < (1 << m); i++) {
        i64 g = 1;
        for (int j = 0; j < m; j++) if (i & (1 << j)) g *= ps[j];
        const i64 h = 2 * n / g;
        const i64 p = extgcd(g, h).first;
        const i64 t = p < 0 ? -p * g : (h - p) * g;
        if (ret > t) ret = t;
    }

    std::cout << ret << std::endl;

    return 0;
}

提出情報

ジャッジ結果