結果
| 問題 | No.2262 Fractions |
| ユーザー |
 nu50218
|
| 提出日時 | 2023-04-08 01:34:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,706 bytes |
| コンパイル時間 | 3,331 ms |
| コンパイル使用メモリ | 231,508 KB |
| 実行使用メモリ | 16,840 KB |
| 最終ジャッジ日時 | 2024-10-02 22:06:07 |
| 合計ジャッジ時間 | 9,740 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
ソースコード
#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;
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();
}