QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139602 | #2058. Generator | As3b_team_f_masr# | AC ✓ | 289ms | 208712kb | C++14 | 1.1kb | 2023-08-14 01:31:22 | 2023-08-14 01:31:24 |
Judging History
answer
#include <bits/stdc++.h>
#define F first
#define S second
#define ld long double
#define EPS 1e-9
using namespace std;
typedef long long ll;
const int N = 1e7+5;
int sq[N];
int p[N],cnt[N];
bool pr[N];
ll pre1[N];
void solve(ll ne,ll de)
{
ll g=__gcd(ne,de);
cout<<ne/g<<"/"<<de/g<<'\n';
}
int main ()
{
ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//freopen("wigz.in","r",stdin);
for(int i=2;i<N;i++)
{
if(!p[i])
{
pr[i]=1;
for(int j=i;j<N;j+=i)
{
if(p[j])continue;
p[j]=i-1;
}
}
}
for(int i=2;i*i<N;i++)
{
sq[i*i]=i-1;
}
for(int i=2;i<N;i++)
{
sq[i]=max(sq[i-1],sq[i]);
ll mn=min(sq[i],p[i]);
cnt[i]=pr[i];
cnt[i]+=cnt[i-1];
pre1[i]+=mn;
pre1[i]+=pre1[i-1];
}
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll ne=pre1[n];
ll de=cnt[n];
solve(ne,de);
}
return(0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 148ms
memory: 208452kb
input:
6 2 3 4 5 6 10
output:
0/1 0/1 1/2 2/3 1/1 2/1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 125ms
memory: 208452kb
input:
99 94 19 4 76 52 37 97 40 75 74 100 14 60 31 78 59 89 44 92 82 83 34 93 27 11 13 80 20 41 56 81 22 17 6 66 90 50 45 42 70 96 8 54 33 72 69 15 55 58 84 91 26 24 98 63 79 64 25 73 5 68 61 71 32 7 67 21 87 85 16 46 3 12 48 99 35 30 65 23 88 77 18 53 2 43 49 36 62 95 47 39 9 28 29 10 38 57 51 86
output:
73/8 3/1 1/2 55/7 98/15 21/4 232/25 67/12 164/21 54/7 236/25 7/3 120/17 49/11 172/21 7/1 26/3 79/14 9/1 183/22 191/23 53/11 109/12 13/3 2/1 13/6 90/11 25/8 72/13 55/8 91/11 7/2 20/7 1/1 15/2 209/24 19/3 81/14 73/13 146/19 28/3 5/4 105/16 52/11 77/10 145/19 8/3 109/16 113/16 192/23 215/24 37/9 32/9 2...
result:
ok 99 lines
Test #3:
score: 0
Accepted
time: 218ms
memory: 208680kb
input:
99900 2497 56404 6523 30336 50376 33939 26032 64717 62283 65761 18224 8180 26686 13140 14359 90006 9898 12282 27452 53030 85977 45808 86582 89595 63812 26485 57806 16240 74874 79832 4636 42205 46690 38615 89049 63950 80274 49942 69229 26034 80271 3047 30313 89598 11707 23950 88186 51506 71768 861 46...
output:
18052/367 1246399/5718 21953/281 532132/3279 355673/1723 621359/3634 431791/2864 752929/3236 1428721/6257 171141/730 88603/696 89482/1027 458/3 85105/781 191705/1683 2372429/8714 29016/305 155253/1469 232273/1500 572391/2705 222697/836 104026/527 2249917/8419 2357222/8675 369723/1600 110577/727 1290...
result:
ok 99900 lines
Test #4:
score: 0
Accepted
time: 284ms
memory: 208712kb
input:
100000 155541 198009 105518 161146 132835 172044 166131 134821 110072 125107 169612 177120 108842 187169 114090 187574 192638 143545 124045 139114 156203 142971 140782 135442 124239 129432 191922 122628 141173 123381 146106 111316 184341 116257 122268 191728 135172 159140 199982 107350 162038 124170...
output:
5059753/14318 7068247/17821 2956192/10067 5311864/14781 4063325/12399 5812767/15670 5536722/15181 4145743/12561 3133769/10460 623247/1957 5695747/15461 6053551/16095 1541907/5173 6537889/16933 3291308/10799 1311685/3394 6804989/17385 4525313/13306 3696657/11653 4332267/12932 1272248/3593 118454/349 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 241ms
memory: 208504kb
input:
100000 209458 203448 220255 223464 231168 245378 206798 236615 253066 231210 231316 266518 266922 264440 244982 227787 217928 294832 245632 231034 294548 221820 259502 210774 278327 212732 217325 225475 266788 214091 243417 240897 225883 267948 221201 212838 254408 266610 233934 286982 292010 214776...
output:
7642477/18758 7338753/18263 8195025/19634 8363261/19900 1461859/3422 9519806/21659 7503719/18529 4525031/10475 9939828/22285 8772523/20534 4388919/10271 10679253/23353 2140399/4677 2112791/4637 2375097/5408 8587535/20248 8073375/19438 2048027/4267 9534743/21683 1752984/4105 6136049/12790 8276935/197...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 285ms
memory: 208612kb
input:
100000 366642 363392 340231 372030 312475 348650 387826 395915 309653 372000 304439 348387 397360 314207 357646 333912 305584 378486 399476 379903 347694 377488 392491 310911 394628 302797 322386 314253 328390 318192 383377 382785 345964 398128 381308 358771 378055 326898 323802 349259 328364 351592...
output:
16659366/31273 16450597/31012 7504459/14601 3398853/6334 13322059/26992 15534323/29871 18008393/32897 18540362/33543 13156691/26777 1416019/2639 12847062/26359 15515951/29845 9316681/16825 13426105/27134 16092440/30571 14623985/28712 12917179/26458 527459/975 9387119/16908 17499417/32291 15472141/29...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 289ms
memory: 208500kb
input:
100000 467700 440544 488378 428164 454364 408708 428398 451976 424732 429292 498191 472191 485700 451766 425732 472955 464032 470351 483485 458107 448423 426944 479291 423609 412772 495998 433417 484416 482579 486427 404538 429771 425589 417334 431639 434138 471105 443380 470390 496571 420069 421799...
output:
23382437/39043 5380517/9246 24846827/40640 1292066/2251 1604727/2717 1937245/3451 20687570/36031 22310192/37873 20446642/35757 6915339/12032 25556003/41397 23705261/39404 24653364/40427 22294115/37853 20512051/35832 23756911/39459 11562756/19379 23569681/39253 24504435/40276 22721030/38323 11029919/...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 208ms
memory: 208656kb
input:
100000 4 761 727 213 604 43 634 224 786 642 349 329 399 936 537 778 856 265 513 426 10 659 820 896 489 120 291 151 469 633 587 774 833 241 17 886 12 207 399 514 875 794 848 619 168 126 250 399 117 428 655 301 323 114 455 439 181 951 668 268 235 288 567 433 167 765 943 226 181 933 693 776 19 968 749 ...
output:
1/2 3691/135 3466/129 673/47 1351/55 39/7 577/23 179/12 3818/137 2925/116 261/14 1201/66 779/39 2407/79 769/33 3780/137 4288/147 113/7 2177/97 846/41 2/1 3049/120 4025/141 2287/77 2041/93 307/30 1028/61 107/9 1952/91 2884/115 2596/107 3772/137 4149/145 804/53 20/7 4511/153 11/5 645/46 779/39 2178/97...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 257ms
memory: 208708kb
input:
100000 214558 316948 43412 540246 510686 359850 665658 775546 285648 707546 27313 736723 102978 36849 796518 860888 716296 547538 760991 399792 662412 735385 37269 706347 597643 895695 892566 864633 12414 386663 309338 618245 664488 318028 466126 530694 292189 401602 387691 684950 859575 951977 3347...
output:
7903722/19175 13590897/27353 290206/1509 28616566/44589 3306480/5293 2705629/5125 38309573/53999 47445577/62139 3922349/8298 41725271/57112 461410/2989 44164724/59283 952943/3284 694964/3907 49260709/63696 27459591/34204 42455765/57769 2650277/4103 46200244/61053 3132765/5641 38043527/53748 11013006...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 268ms
memory: 208548kb
input:
100000 8506895 3311677 976283 147086 7990471 5571270 7417640 8043005 9525468 9777660 3500181 2702477 2508228 2578363 1945758 3073211 6057821 5779085 6466011 6879230 8357574 3033387 8630102 3808173 8457557 7582863 5825370 1070707 5105440 4094555 8924812 7696038 9717068 2151215 7897597 6830426 6300981...
output:
1388355137/571554 365506411/237683 65522521/76815 4678786/13597 317630566/134797 762308674/385365 1143398591/503077 1282302181/542460 543318502/211723 563855578/216955 395133857/250158 137163253/98405 20576294/15303 256718323/188404 172710669/145217 109605439/73894 95351818/46285 401388643/199330 94...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 279ms
memory: 208544kb
input:
100000 7522059 1813943 6830390 12658 536037 6861964 4347549 2860294 2967088 3212798 4638554 8023955 9243241 9225557 4303691 5475132 1903311 2482484 4511693 7249650 4087063 9591493 818945 240641 6124720 3230511 3368769 3137362 9808142 7781827 6609767 4647122 3509312 4989615 2953208 1153909 7243092 72...
output:
1166207669/509643 156415220/136041 203436136/93163 53981/504 28304906/44271 1023868617/467842 268339917/152962 99072955/69154 312942121/214597 350197914/231091 196077413/108320 639019004/270637 1561984796/617637 1557742427/616524 264539334/151543 743814892/379199 294199/250 121667752/90939 565647475...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 274ms
memory: 208540kb
input:
100000 8042519 6802809 9568764 8423987 8960333 4098104 2790878 3976936 8895104 4175929 8065027 6651990 1900337 3852895 5675368 1754838 8199803 9804159 4569529 2553536 9172720 8003876 9532390 7074104 1668074 1649776 1348793 8919763 5296372 963693 141977 6936471 8405022 9408721 2251179 5535452 1126363...
output:
1282186084/542427 505674236/232029 820231695/318926 1369249424/566385 1494639925/599994 54862913/32183 71759089/50683 473234170/281667 1479232014/595915 507026302/294723 1287333047/543871 979740209/454455 55679217/47351 226264435/136751 782435549/391998 149307899/131954 439300437/184102 1698109493/6...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 282ms
memory: 208540kb
input:
100000 5682436 8827086 3801758 2651461 9068479 2402700 7470496 7346358 3251813 5689594 7758364 8947208 9809899 8017858 5380235 2125563 8891797 9735750 1614801 9738130 419784 2671674 7946365 9459756 7231720 5775239 6954712 9859510 2907138 8987598 2556778 8857009 4438981 1773267 6491313 8324630 558551...
output:
783799051/392442 209042508/84529 444029019/270104 267060597/193355 760086139/303346 116198381/88237 1154944225/506403 1127862581/498570 356223105/233701 785204537/392902 1218499254/524557 1491555350/599189 849766124/326443 319163660/135223 241874715/124361 195559459/157558 1478393900/595693 84067870...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 285ms
memory: 208712kb
input:
100000 9845611 9881499 9886423 9881292 9898705 9827455 9844209 9879122 9884820 9849364 9896221 9810439 9846884 9819334 9814789 9861469 9812569 9825075 9829484 9812147 9865377 9828776 9808509 9862442 9877723 9818671 9863770 9800048 9835862 9879841 9872492 9879705 9892297 9840588 9892683 9816536 98248...
output:
569422939/218358 1717062095/657294 859137193/328797 858499247/328639 1721321941/658370 1703855079/653980 284657381/109166 1716467227/657144 1717879601/657500 1709209482/655321 860354581/329107 1699657465/652917 244086794/93595 1701846655/653478 188966196/72575 1712171443/656069 1700154803/653042 567...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 273ms
memory: 208664kb
input:
100000 9966724 9945026 9927840 9935542 9975430 9942257 9916645 9998851 9965506 9960872 9940313 9924430 9980241 9954679 9991502 9913306 9992714 9964584 9918721 9990692 9956924 9995236 9994746 9914490 9942525 9998621 9972911 9965615 9987994 9990806 9986001 9976916 9949323 9955856 9963545 9963599 99446...
output:
1738070527/662557 866367984/330611 1728464794/660145 865205763/330322 1740207243/663092 1732076057/661058 1725724780/659469 1745953302/664517 1737734337/662473 4266872/1627 1731576928/660935 1727626333/659937 1741416023/663390 1735106470/661819 872057924/332029 574964370/219751 22654474/8625 1737514...
result:
ok 100000 lines