結果
問題 | No.2262 Fractions |
ユーザー |
|
提出日時 | 2023-04-07 22:50:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,655 ms / 2,000 ms |
コード長 | 1,828 bytes |
コンパイル時間 | 1,721 ms |
コンパイル使用メモリ | 195,496 KB |
最終ジャッジ日時 | 2025-02-12 02:13:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#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;}void solve(){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;return;}tot = dp[1];}bool inv = false;if (k * 2 > tot){k = tot - k + 1;inv = true;}{ll l = 0, r = n * n + 10;while (r - l > 1){ll x = (l + r) / 2;for (ll i = n; i >= 1; i--){dp[i] = 0;ll m = n / i;for (int a = 1; a <= m; a++)dp[i] += min(m, a * x / (n * n));for (ll j = i * 2; j <= n; j += i)dp[i] -= dp[j];}if (dp[1] < k){l = x;}else{r = x;}}for (ll a = 1; a <= n; a++){ll x = a * l / n / n + 1;ll y = a * r / n / n;if (x == y){if (!inv){cout << y << "/" << a;}else{cout << a << "/" << y;}return;}}}}int main(){int t;cin >> t;while (t--){solve();if (t){cout << "\n";}else{cout << endl;}}}