結果
問題 | No.2262 Fractions |
ユーザー |
|
提出日時 | 2023-04-08 01:34:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,706 bytes |
コンパイル時間 | 10,183 ms |
コンパイル使用メモリ | 287,340 KB |
最終ジャッジ日時 | 2025-02-12 03:43:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 1 |
other | AC * 31 WA * 4 TLE * 10 |
ソースコード
#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)#endifusing 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;double val = (double)A / (double)B;if (abs(val - imax) < 1e-12 && 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();}