結果
問題 | No.2262 Fractions |
ユーザー | chro_96 |
提出日時 | 2023-04-07 22:58:07 |
言語 | C (gcc 12.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,286 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 32,768 KB |
実行使用メモリ | 33,292 KB |
最終ジャッジ日時 | 2024-10-02 20:17:11 |
合計ジャッジ時間 | 27,131 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | AC | 496 ms
26,468 KB |
testcase_02 | AC | 517 ms
26,416 KB |
testcase_03 | AC | 524 ms
26,276 KB |
testcase_04 | AC | 529 ms
26,496 KB |
testcase_05 | AC | 532 ms
26,472 KB |
testcase_06 | AC | 551 ms
26,340 KB |
testcase_07 | AC | 547 ms
26,348 KB |
testcase_08 | AC | 537 ms
26,496 KB |
testcase_09 | AC | 555 ms
26,396 KB |
testcase_10 | AC | 553 ms
26,472 KB |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 1,952 ms
26,496 KB |
testcase_16 | AC | 746 ms
26,392 KB |
testcase_17 | AC | 739 ms
26,476 KB |
testcase_18 | AC | 728 ms
26,472 KB |
testcase_19 | TLE | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
ソースコード
#include <stdio.h> int main () { int t = 0; int res = 0; long long ps[300001][10] = {}; int pcnt[300001] = {}; for (int i = 2LL; i <= 300000; i++) { int tmp = i; for (int p = 2; p*p <= i; p++) { if (tmp%p == 0) { ps[i][pcnt[i]] = p; pcnt[i]++; while (tmp%p == 0) { tmp /= p; } } } if (tmp > 1) { ps[i][pcnt[i]] = tmp; pcnt[i]++; } } res = scanf("%d", &t); while (t > 0) { long long n = 0LL; long long k = 0LL; long long ans[2] = { 1LL, 0LL }; long long l[2] = { 0LL, 1LL }; res = scanf("%lld", &n); res = scanf("%lld", &k); while (l[0]+ans[0] <= n && l[1]+ans[1] <= n) { long long nxt[2] = { l[0]+ans[0], l[1]+ans[1] }; long long cnt = 0LL; for (long long i = 1LL; i <= n; i += 1LL) { long long d = (nxt[0]*i)/nxt[1]; long long diff = 0LL; if (d > n) { d = n; } for (int j = 1; j < (1<<pcnt[(int)i]); j++) { int bcnt = 0; long long p = 1LL; for (int l = 0; l < pcnt[(int)i]; l++) { if ((j&(1<<l)) > 0) { p *= ps[(int)i][l]; bcnt++; } } if (bcnt%2 == 1) { diff += d/p; } else { diff -= d/p; } } cnt += d-diff; } /*if (cnt < k) { l[0] += ans[0]; l[1] += ans[1]; } else { ans[0] += l[0]; ans[1] += l[1]; }*/ if (cnt < k) { long long t[2] = { 1LL, n }; if (t[1] > (n-l[0])/ans[0]) { t[1] = (n-l[0])/ans[0]; } if (ans[1] > 0LL && t[1] > (n-l[1])/ans[1]) { t[1] = (n-l[1])/ans[1]; } t[1] += 1LL; while (t[1]-t[0] > 1LL) { long long nxt_v = (t[0]+t[1])/2LL; long long nxt[2] = { l[0]+nxt_v*ans[0], l[1]+nxt_v*ans[1] }; long long cnt = 0LL; for (long long i = 1LL; i <= n; i += 1LL) { long long d = (nxt[0]*i)/nxt[1]; long long diff = 0LL; if (d > n) { d = n; } for (int j = 1; j < (1<<pcnt[(int)i]); j++) { int bcnt = 0; long long p = 1LL; for (int l = 0; l < pcnt[(int)i]; l++) { if ((j&(1<<l)) > 0) { p *= ps[(int)i][l]; bcnt++; } } if (bcnt%2 == 1) { diff += d/p; } else { diff -= d/p; } } cnt += d-diff; } if (cnt < k) { t[0] = nxt_v; } else { t[1] = nxt_v; } } l[0] += t[0]*ans[0]; l[1] += t[0]*ans[1]; } else { long long t[2] = { 1LL, n }; if (l[0] > 0LL && t[1] > (n-ans[0])/l[0]) { t[1] = (n-ans[0])/l[0]; } if (t[1] > (n-ans[1])/l[1]) { t[1] = (n-ans[1])/l[1]; } t[1] += 1LL; while (t[1]-t[0] > 1LL) { long long nxt_v = (t[0]+t[1])/2LL; long long nxt[2] = { nxt_v*l[0]+ans[0], nxt_v*l[1]+ans[1] }; long long cnt = 0LL; for (long long i = 1LL; i <= n; i += 1LL) { long long d = (nxt[0]*i)/nxt[1]; long long diff = 0LL; if (d > n) { d = n; } for (int j = 1; j < (1<<pcnt[(int)i]); j++) { int bcnt = 0; long long p = 1LL; for (int l = 0; l < pcnt[(int)i]; l++) { if ((j&(1<<l)) > 0) { p *= ps[(int)i][l]; bcnt++; } } if (bcnt%2 == 1) { diff += d/p; } else { diff -= d/p; } } cnt += d-diff; } if (cnt >= k) { t[0] = nxt_v; } else { t[1] = nxt_v; } } ans[0] += t[0]*l[0]; ans[1] += t[0]*l[1]; } } if (ans[1] == 0LL) { printf("-1\n"); } else { printf("%lld/%lld\n", ans[0], ans[1]); } t--; } return 0; }