結果

問題 No.2262 Fractions
ユーザー KumaTachiRenKumaTachiRen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 long
template <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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0