QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#842920 | #9962. Diminishing Fractions | ucup-team5243# | TL | 1971ms | 13436kb | Python3 | 1.4kb | 2025-01-04 15:59:36 | 2025-01-04 15:59:39 |
Judging History
answer
MOD = 998244353
primes = []
sieve = [1] * 50001
ZZ = 50000
for p in range(2,ZZ+1):
if sieve[p] != 1:
continue
q = p*p
while q <= ZZ:
sieve[q] = 0
q += p
for p in range(2,ZZ+1):
if sieve[p] == 1:
primes.append(p)
T = int(input())
for t in range(T):
N = int(input())
if N == 1 :
print("1/1")
continue
A = []
for p in primes:
if p <= N:
q = p
while q*p <= N:
q*=p
A.append(q)
N = len(A)
X = [-1]*N
Y = [-1]*N
for i in range(N-1) :
X.append(i*2)
Y.append(i*2+1)
n = len(X)
Z = [0] * n
Z[-1] = 1
for i in range(N,n):
A.append(A[X[i]] * A[Y[i]])
for i in range(n-1,N-1,-1):
Z[X[i]] = Z[i] * A[Y[i]] % A[X[i]]
Z[Y[i]] = Z[i] * A[X[i]] % A[Y[i]]
# print(Z)
# print(A)
Q = [pow(Z[i],-1,A[i]) for i in range(N)]
f = 0
g = 1
for i in range(N):
a = pow(A[i],-1,MOD)
f = (f+a*Q[i])%MOD
g = g*a%MOD
p = (f-g)%MOD
for i in range(N):
if i+p>=N :
print(Q[i]-A[i], end="")
else:
if i != 0:
print("+",end="")
print(Q[i],end="")
print("/",end="")
print(A[i],end="")
print("")
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 27ms
memory: 11004kb
input:
2 3 6
output:
1/2-1/3 3/4-1/3-2/5
result:
ok OK, t = 2
Test #2:
score: 0
Accepted
time: 26ms
memory: 11020kb
input:
1 1
output:
1/1
result:
ok OK, t = 1
Test #3:
score: 0
Accepted
time: 25ms
memory: 10996kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1/1 1/2 1/2-1/3 3/4-2/3 3/4-1/3-2/5 3/4-1/3-2/5 1/4+2/3-1/5-5/7 1/8+1/3+2/5-6/7 3/8+1/9-1/5-2/7 3/8+1/9-1/5-2/7
result:
ok OK, t = 10
Test #4:
score: 0
Accepted
time: 27ms
memory: 11096kb
input:
54 7 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 3 47 81
output:
1/4+2/3-1/5-5/7 15/16+5/9+3/5-5/7-2/11-9/13-5/17-4/19 1/2 1/2-1/3 3/4-2/3 3/4-1/3-2/5 3/4-1/3-2/5 1/4+2/3-1/5-5/7 1/8+1/3+2/5-6/7 3/8+1/9-1/5-2/7 3/8+1/9-1/5-2/7 1/8+5/9+4/5-4/7-10/11 1/8+5/9+4/5-4/7-10/11 5/8+8/9-2/5-3/7-5/11-3/13 5/8+8/9-2/5-3/7-5/11-3/13 5/8+8/9-2/5-3/7-5/11-3/13 13/16+4/9+4/5-5/...
result:
ok OK, t = 54
Test #5:
score: 0
Accepted
time: 43ms
memory: 11172kb
input:
92 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 255 258 261 264 267 270 273 276 279 282 28...
output:
27/32+2/27+21/25+26/49+10/11+2/13-6/17-11/19-4/23-5/29-13/31-16/37-15/41-13/43-26/47 15/32+25/27+7/25+31/49+6/11+2/13+14/17+17/19-17/23-28/29-2/31-1/37-32/41-40/43-20/47-42/53 15/32+25/27+7/25+31/49+6/11+2/13+14/17+17/19-17/23-28/29-2/31-1/37-32/41-40/43-20/47-42/53 29/32+5/27+23/25+8/49+7/11+4/13+6...
result:
ok OK, t = 92
Test #6:
score: 0
Accepted
time: 429ms
memory: 11372kb
input:
1000 622 149 839 472 292 345 799 941 449 15 907 494 48 430 505 66 83 97 10 548 286 644 528 249 573 860 557 932 746 262 971 157 603 715 984 333 53 916 784 649 70 768 780 64 118 616 979 466 24 2 517 774 566 419 182 222 40 169 951 830 977 383 355 770 134 973 917 3 854 31 35 825 109 945 671 536 952 888 ...
output:
169/512+106/243+2/125+190/343+95/121+11/169+288/289+24/361+355/529+7/29+21/31+28/37+15/41+25/43+41/47+4/53+18/59+51/61+50/67+18/71+66/73+47/79+77/83+82/89+85/97+90/101+11/103+66/107+76/109+28/113+16/127+91/131+34/137+23/139+7/149+129/151+75/157+8/163+20/167+70/173+138/179+40/181+130/191+120/193+14/1...
result:
ok OK, t = 1000
Test #7:
score: 0
Accepted
time: 819ms
memory: 11380kb
input:
1000 1748 1741 1576 1940 1648 1825 1183 1447 1318 1277 1913 1208 1417 1388 1143 1581 1222 1904 1407 1006 1175 1218 1734 1934 1003 1704 1984 1399 1333 1840 1317 1233 1133 1232 1776 1881 1476 1712 1401 1231 1978 1964 1419 1644 1103 1498 1454 1480 1377 1352 1837 1616 1009 1413 1199 1977 1477 1579 1920 ...
output:
275/1024+410/729+319/625+190/343+1226/1331+162/169+114/289+169/361+302/529+370/841+7/961+299/1369+958/1681+21/43+23/47+47/53+14/59+19/61+57/67+26/71+14/73+20/79+43/83+65/89+63/97+7/101+60/103+88/107+4/109+107/113+92/127+84/131+20/137+77/139+142/149+64/151+108/157+91/163+104/167+49/173+20/179+110/181...
result:
ok OK, t = 1000
Test #8:
score: 0
Accepted
time: 1245ms
memory: 11560kb
input:
1000 2107 2115 2985 2832 2564 2529 2971 2637 2666 2172 2496 2191 2465 2199 2260 2161 2402 2369 2762 2674 2734 2252 2488 2185 2652 2014 2018 2960 2313 2063 2696 2976 2457 2247 2180 2647 2907 2901 2912 2538 2512 2623 2267 2986 2348 2170 2131 2166 2563 2111 2860 2254 2462 2080 2054 2803 2397 2778 2411 ...
output:
85/2048+596/729+193/625+214/343+167/1331+18/169+103/289+124/361+275/529+487/841+532/961+1087/1369+582/1681+91/1849+14/47+31/53+57/59+58/61+22/67+54/71+35/73+41/79+33/83+26/89+29/97+43/101+23/103+54/107+55/109+57/113+67/127+58/131+38/137+115/139+5/149+52/151+102/157+97/163+146/167+124/173+157/179+177...
result:
ok OK, t = 1000
Test #9:
score: 0
Accepted
time: 1598ms
memory: 11576kb
input:
1000 3416 3784 3793 3610 3982 3174 3253 3088 3197 3926 3664 3669 3431 3821 3340 3298 3498 3627 3194 3354 3362 3512 3865 3529 3988 3973 3852 3552 3672 3282 3035 3639 3998 3090 3771 3618 3402 3139 3903 3110 3452 3947 3941 3225 3187 3283 3243 3722 3808 3491 3309 3935 3937 3259 3909 3665 3809 3390 3285 ...
output:
921/2048+1583/2187+3038/3125+2063/2401+101/1331+1412/2197+73/289+102/361+7/529+24/841+637/961+849/1369+1339/1681+931/1849+322/2209+2764/2809+30/59+58/61+10/67+1/71+37/73+10/79+11/83+81/89+37/97+29/101+54/103+20/107+20/109+23/113+21/127+106/131+102/137+43/139+17/149+41/151+22/157+48/163+104/167+30/17...
result:
ok OK, t = 1000
Test #10:
score: 0
Accepted
time: 1765ms
memory: 11656kb
input:
899 4695 4616 4545 4771 4315 4850 4821 4722 4493 4338 4566 4144 4721 4334 4536 4313 4264 4669 4648 4780 4551 4044 4506 4798 4483 4372 4371 4636 4650 4590 4340 4383 4756 4104 4077 4067 4692 4008 4141 4610 4532 4751 4345 4498 4214 4621 4519 4505 4681 4726 4011 4879 4103 4283 4470 4844 4520 4740 4333 4...
output:
2597/4096+1553/2187+487/3125+1742/2401+651/1331+144/2197+275/289+177/361+252/529+439/841+537/961+1060/1369+627/1681+547/1849+587/2209+1847/2809+554/3481+1664/3721+2220/4489+10/71+44/73+65/79+13/83+21/89+71/97+39/101+91/103+55/107+90/109+101/113+45/127+98/131+70/137+101/139+70/149+87/151+10/157+22/16...
result:
ok OK, t = 899
Test #11:
score: 0
Accepted
time: 1755ms
memory: 13036kb
input:
1000 3798 4097 3356 3197 4364 3360 3927 4704 4072 3229 3681 3276 4187 4013 4014 3134 3743 3208 4792 3235 4788 3953 3313 4147 3230 3497 3181 4376 4631 3710 3602 4191 3405 3381 4722 3607 4374 3037 3149 3682 3557 3338 4471 3242 4470 4753 4637 3343 3625 4516 3505 3553 3626 3073 3222 4514 4402 4063 3372 ...
output:
2037/2048+1064/2187+3074/3125+527/2401+772/1331+1793/2197+172/289+60/361+29/529+791/841+827/961+1154/1369+1633/1681+1084/1849+327/2209+482/2809+122/3481+2786/3721+53/67+55/71+43/73+55/79+59/83+5/89+57/97+99/101+17/103+56/107+17/109+51/113+115/127+58/131+19/137+129/139+4/149+55/151+56/157+1/163+131/1...
result:
ok OK, t = 1000
Test #12:
score: 0
Accepted
time: 1818ms
memory: 13368kb
input:
474 7545 5913 9012 7937 9033 8958 6042 9802 6773 7104 7992 7475 7128 5208 6469 5645 7483 49664 7929 9114 8828 7916 9405 6829 8448 8454 9204 7795 5960 6310 9545 49393 8789 5482 8149 7405 8428 7210 5902 8761 5209 8251 7599 9264 5237 8710 6878 8842 5430 9871 8230 8959 9001 8926 9201 5003 8737 7628 7133...
output:
117/4096+4606/6561+2117/3125+1928/2401+488/1331+1865/2197+2833/4913+40/6859+58/529+437/841+944/961+970/1369+92/1681+477/1849+1977/2209+860/2809+1892/3481+1004/3721+769/4489+3978/5041+1939/5329+3261/6241+547/6889+62/89+76/97+29/101+65/103+89/107+63/109+37/113+62/127+82/131+59/137+127/139+40/149+61/15...
result:
ok OK, t = 474
Test #13:
score: 0
Accepted
time: 1875ms
memory: 13312kb
input:
505 654 4006 658 39050 749 2525 45144 8 107 366 181 1161 49410 315 24 1125 56 2895 4689 19600 861 18 17643 27130 4321 20973 43326 5761 3127 514 4286 286 55 4733 1114 1022 540 15500 47 158 2168 529 428 41729 1778 83 53 904 416 25550 134 475 2624 386 13073 4799 16 484 27746 7 35604 37 1814 1384 45 377...
output:
99/512+136/243+149/625+251/343+35/121+147/169+251/289+162/361+74/529+7/29+11/31+13/37+8/41+28/43+42/47+30/53+24/59+41/61+4/67+58/71+31/73+6/79+68/83+60/89+69/97+51/101+80/103+65/107+3/109+16/113+21/127+70/131+46/137+21/139+144/149+98/151+156/157+133/163+60/167+58/173+177/179+153/181+148/191+77/193+1...
result:
ok OK, t = 505
Test #14:
score: 0
Accepted
time: 1948ms
memory: 13436kb
input:
164 5348 13781 10630 42085 48735 22502 30143 8994 17829 40332 4188 40168 2858 4539 27532 42223 44889 33093 47647 8530 48824 812 14976 32746 29270 44536 33166 2354 27686 630 43523 32120 38166 6687 1125 45588 46641 42232 29120 11682 17398 3236 7499 48684 43474 11053 182 13451 43129 35818 15957 11254 4...
output:
757/4096+674/2187+989/3125+2301/2401+18/1331+1102/2197+131/4913+344/361+393/529+127/841+439/961+587/1369+1393/1681+930/1849+509/2209+2570/2809+1943/3481+413/3721+2705/4489+4721/5041+3510/5329+27/79+39/83+51/89+46/97+93/101+95/103+95/107+63/109+5/113+113/127+90/131+67/137+77/139+96/149+123/151+71/157...
result:
ok OK, t = 164
Test #15:
score: 0
Accepted
time: 1971ms
memory: 13316kb
input:
156 11299 49780 39754 44360 13750 33643 31382 48665 22685 25974 3679 15594 20849 11844 40645 20943 26660 48724 29993 21829 26251 7053 15218 29474 31529 31754 2823 4866 17437 40827 38285 3116 32140 37739 3831 29989 28174 13666 24668 41569 45278 43765 47564 39670 35238 28460 21784 45880 9557 38904 499...
output:
7077/8192+1588/6561+2944/3125+1969/2401+1006/1331+451/2197+3797/4913+2370/6859+433/529+443/841+879/961+283/1369+73/1681+1683/1849+606/2209+2253/2809+2900/3481+145/3721+3386/4489+2917/5041+2070/5329+3527/6241+3736/6889+3230/7921+4302/9409+8038/10201+9430/10609+68/107+4/109+89/113+23/127+13/131+49/137...
result:
ok OK, t = 156
Test #16:
score: -100
Time Limit Exceeded
input:
89 42615 41319 46294 44842 45088 40377 45143 42991 47088 47811 44569 40910 41531 49894 45027 47842 48327 48243 49764 46548 46950 41965 49765 49084 41705 40820 48320 46963 42990 42063 42431 46354 40397 39081 47952 45441 41398 40985 45235 47640 44526 41162 40397 47458 46986 49919 45345 49801 43912 425...
output:
41/32768+17947/19683+424/15625+2904/16807+2264/14641+28519/28561+1497/4913+6735/6859+6549/12167+23058/24389+26650/29791+1224/1369+380/1681+850/1849+831/2209+1539/2809+2329/3481+3092/3721+4121/4489+4997/5041+3755/5329+4319/6241+5786/6889+1992/7921+1650/9409+6919/10201+7956/10609+6279/11449+10783/1188...