結果
| 問題 | No.2262 Fractions |
| ユーザー |
 chro_96
|
| 提出日時 | 2023-04-07 23:22:30 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,201 bytes |
| コンパイル時間 | 317 ms |
| コンパイル使用メモリ | 30,720 KB |
| 実行使用メモリ | 39,924 KB |
| 最終ジャッジ日時 | 2024-10-02 20:36:05 |
| 合計ジャッジ時間 | 6,618 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| 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 = 2; i <= 300000; i++) {
if (pcnt[i] <= 0) {
ps[i][0] = (long long)i;
pcnt[i] = 1;
for (int p = 2; i*p <= 300000; p++) {
ps[i*p][pcnt[i*p]] = i;
pcnt[i*p]++;
}
}
}
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;
}