結果
問題 | No.2262 Fractions |
ユーザー |
|
提出日時 | 2023-04-07 22:29:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,957 bytes |
コンパイル時間 | 6,217 ms |
コンパイル使用メモリ | 256,860 KB |
最終ジャッジ日時 | 2025-02-12 01:52:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 21 TLE * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Fast{Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define ll long longtemplate <typename T>bool chmax(T &a, const T &b){if (a < b){a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T &b){if (a > b){a = b;return true;}return false;}int main(){int t;cin >> t;while (t--){ll n, k;cin >> n >> k;vector<ll> dp(n + 1, 0);ll tot = 0;{for (int i = 1; i <= n; i++)dp[i] = (n / i) * (n / i);for (ll i = n; i >= 1; i--)for (ll j = i * 2; j <= n; j += i)dp[i] -= dp[j];if (dp[1] < k){cout << -1 << "\n";continue;}tot = dp[1];}if (k == (tot + 1) / 2){cout << "1/1\n";continue;;}bool inv = false;if (k > (tot + 1) / 2){k = tot - k + 1;inv = true;}{ll l = 0, r = n * n;while (r - l > 1){ll x = (l + r) / 2;for (int i = 1; i <= n; i++){dp[i] = 0;for (int a = i; a <= n; a += i)dp[i] += min(n, a * x / (n * n)) / i;}for (ll i = n; i >= 1; i--)for (ll j = i * 2; j <= n; j += i)dp[i] -= dp[j];if (dp[1] < k)l = x;elser = x;}for (long a = 1; a <= n; a++){long x = a * l / n / n + 1;long y = a * r / n / n;if (x == y){if (!inv){cout << y << "/" << a << "\n";}else{cout << a << "/" << y << "\n";}break;}}}}cout << endl;}