結果
問題 | No.2262 Fractions |
ユーザー | jiangly |
提出日時 | 2023-04-07 22:21:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,722 bytes |
コンパイル時間 | 2,283 ms |
コンパイル使用メモリ | 208,516 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-10-02 19:50:10 |
合計ジャッジ時間 | 12,065 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
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 | 10 ms
9,344 KB |
testcase_38 | AC | 10 ms
9,216 KB |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
ソースコード
#include <bits/stdc++.h>using i64 = long long;std::vector<int> minp, primes, phi, mu;std::vector<i64> sphi;void sieve(int n) {minp.assign(n + 1, 0);phi.assign(n + 1, 0);sphi.assign(n + 1, 0);mu.assign(n + 1, 0);primes.clear();phi[1] = 1;mu[1] = 1;for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;phi[i] = i - 1;mu[i] = -1;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {phi[i * p] = phi[i] * p;break;}phi[i * p] = phi[i] * (p - 1);mu[i * p] = -mu[i];}}for (int i = 1; i <= n; i++) {sphi[i] = sphi[i - 1] + phi[i];mu[i] += mu[i - 1];}}std::pair<i64, i64> get(int N, int x, int y) {if (x > y) {auto [lt, le] = get(N, y, x);std::tie(lt, le) = std::pair(2 * sphi[N] - 1 - le, 2 * sphi[N] - 1 - lt);return {lt, le};}i64 le = 0, lt;for (int i = 1; i <= N; i++) {le += 1LL * x * i / y * mu[N / i];}lt = le - (x <= N && y <= N && std::gcd(x, y) == 1);return {lt, le};}void solve() {int N;i64 K;std::cin >> N >> K;K--;if (K >= 2 * sphi[N] - 1) {std::cout << -1 << "\n";return;}int lox = 0, loy = 1, hix = 1, hiy = 0;while (true) {auto [lt, le] = get(N, lox + hix, loy + hiy);if (lt <= K && le > K) {std::cout << lox + hix << " " << loy + hiy << "\n";return;}if (le <= K) {int t = 1;while (get(N, lox + hix * t, loy + hiy * t).second <= K) {t *= 2;}while (t > 1) {t /= 2;if (get(N, lox + hix * t, loy + hiy * t).second <= K) {lox += hix * t;loy += hiy * t;}}} else {int t = 1;while (get(N, lox * t + hix, loy * t + hiy).first > K) {t *= 2;}while (t > 1) {t /= 2;if (get(N, lox * t + hix, loy * t + hiy).first > K) {hix += lox * t;hiy += loy * t;}}}}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);sieve(3E5);int t;std::cin >> t;while (t--) {solve();}return 0;}