結果

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

ソースコード

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;
}
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;
else
r = 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0