結果

問題 No.2262 Fractions
ユーザー nu50218nu50218
提出日時 2023-04-08 01:36:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,705 bytes
コンパイル時間 3,339 ms
コンパイル使用メモリ 230,384 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-02 22:07:49
合計ジャッジ時間 23,824 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 364 ms
5,248 KB
testcase_01 AC 187 ms
5,248 KB
testcase_02 AC 162 ms
5,248 KB
testcase_03 AC 155 ms
5,248 KB
testcase_04 AC 159 ms
5,248 KB
testcase_05 AC 144 ms
5,248 KB
testcase_06 AC 159 ms
5,248 KB
testcase_07 AC 153 ms
5,248 KB
testcase_08 AC 139 ms
5,248 KB
testcase_09 AC 149 ms
5,248 KB
testcase_10 AC 150 ms
5,248 KB
testcase_11 AC 279 ms
5,248 KB
testcase_12 AC 280 ms
5,248 KB
testcase_13 AC 283 ms
5,248 KB
testcase_14 AC 279 ms
5,248 KB
testcase_15 AC 279 ms
5,248 KB
testcase_16 AC 193 ms
5,248 KB
testcase_17 AC 193 ms
5,248 KB
testcase_18 AC 191 ms
5,248 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 AC 358 ms
5,248 KB
testcase_38 AC 367 ms
5,248 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL
#include <local.hpp>
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2")
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define postprocess(...) ((void)0)
#endif

using namespace std;
using ll = long long;
using ld = long double;

#line 2 "multiplicative-function/divisor-multiple-transform.hpp"

#line 2 "prime/prime-enumerate.hpp"

// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
    vector<bool> sieve(N / 3 + 1, 1);
    for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
        if (!sieve[i]) continue;
        for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
                 qe = sieve.size();
             q < qe; q += r = s - r)
            sieve[q] = 0;
    }
    vector<int> ret{2, 3};
    for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
        if (sieve[i]) ret.push_back(p);
    while (!ret.empty() && ret.back() > N) ret.pop_back();
    return ret;
}
#line 6 "multiplicative-function/divisor-multiple-transform.hpp"

struct divisor_transform {
    template <typename T>
    static void zeta_transform(vector<T> &a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto &p : sieve)
            for (int k = 1; k * p <= N; ++k) a[k * p] += a[k];
    }
    template <typename T>
    static void mobius_transform(T &a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto &p : sieve)
            for (int k = N / p; k > 0; --k) a[k * p] -= a[k];
    }

    template <typename T>
    static void zeta_transform(map<long long, T> &a) {
        for (auto p = rbegin(a); p != rend(a); p++)
            for (auto &x : a) {
                if (p->first == x.first) break;
                if (p->first % x.first == 0) p->second += x.second;
            }
    }
    template <typename T>
    static void mobius_transform(map<long long, T> &a) {
        for (auto &x : a)
            for (auto p = rbegin(a); p != rend(a); p++) {
                if (x.first == p->first) break;
                if (p->first % x.first == 0) p->second -= x.second;
            }
    }
};

struct multiple_transform {
    template <typename T>
    static void zeta_transform(vector<T> &a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto &p : sieve)
            for (int k = N / p; k > 0; --k) a[k] += a[k * p];
    }
    template <typename T>
    static void mobius_transform(vector<T> &a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto &p : sieve)
            for (int k = 1; k * p <= N; ++k) a[k] -= a[k * p];
    }

    template <typename T>
    static void zeta_transform(map<long long, T> &a) {
        for (auto &x : a)
            for (auto p = rbegin(a); p->first != x.first; p++)
                if (p->first % x.first == 0) x.second += p->second;
    }
    template <typename T>
    static void mobius_transform(map<long long, T> &a) {
        for (auto p1 = rbegin(a); p1 != rend(a); p1++)
            for (auto p2 = rbegin(a); p2 != p1; p2++)
                if (p2->first % p1->first == 0) p1->second -= p2->second;
    }
};

/**
 * @brief 倍数変換・約数変換
 * @docs docs/multiplicative-function/divisor-multiple-transform.md
 */

template <typename mint>
vector<mint> gcd_convolution(const vector<mint> &a, const vector<mint> &b) {
    assert(a.size() == b.size());
    auto s = a, t = b;
    multiple_transform::zeta_transform(s);
    multiple_transform::zeta_transform(t);
    for (int i = 0; i < (int)a.size(); i++) s[i] *= t[i];
    multiple_transform::mobius_transform(s);
    return s;
}

/**
 * @brief GCD畳み込み
 */

int64_t euler_phi(int64_t n) {
    int64_t ret = n;
    for (int64_t i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

using rational = tuple<ll, ll, ll, ll>;

rational left(rational cur) {
    auto [a, b, c, d] = cur;
    return {a, b, (a + c), (b + d)};
}

rational right(rational cur) {
    auto [a, b, c, d] = cur;
    return {(a + c), (b + d), c, d};
}

void solve([[maybe_unused]] int test) {
    ll N, K;
    cin >> N >> K;

    ll less_than_1 = 0;
    for (int i = 2; i <= N; i++) {
        less_than_1 += euler_phi(i);
    }

    if (less_than_1 + 1 + less_than_1 < K) {
        cout << -1 << endl;
        return;
    }

    bool reverse = false;
    if (less_than_1 + 1 < K) {
        reverse = true;
        K = less_than_1 + 1 + less_than_1 - K + 1;
    }

    ld imin = 0;
    ld imax = N;

    while (imax - imin > 1e-12) {
        ld imid = (imax + imin) / 2.0l;

        vector<uint64_t> g(N + 1, 0);
        for (ll i = 1; i <= N; i++) {
            g[i] = floor(imid * i + 1e-9);
        }

        divisor_transform::mobius_transform(g);

        ll cnt = accumulate(g.begin() + 1, g.end(), 0ul);

        (cnt >= K ? imax : imin) = imid;
    }

    auto cur = rational{0, 1, 1, 0};

    while (true) {
        auto [a, b, c, d] = cur;

        ll A = a + c;
        ll B = b + d;

        ld val = (ld)A / (ld)B;

        if (max(val - imax, imax - val) < 1e-8 && gcd(A, B) == 1) {
            if (reverse) swap(A, B);
            cout << A << '/' << B << endl;
            return;
        }

        if (imax < val) {
            cur = left(cur);
        } else {
            cur = right(cur);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }

    postprocess();
}
0