OneGcd

SRM 779 · 2020-02-20 · by lazy_fox

SRM 779 · 2020-02-20 · by lazy_fox · Math

Show categories

Class Name: OneGcd

Return Type: int[]

Method Name: solve

Arg Types: (vector<long long>, vector<int>)

Problem Statement

The greatest common divisor of two positive integers p and q, denoted gcd(p,q), is the largest d such that d divides p and d divides q. Two positive integers p and q are called coprime if their greatest common divisor is 1. For example, 15 and 44 are coprime but 21 and 35 are not (because gcd(21,35) = 7).

You are given N queries. The parameters for these queries are given in the long[] X and in the int[] Y. These contain N elements each.

For each valid i, answer the following query: Let x = X[i] and y = Y[i]. Consider the closed interval [x, x+y-1]. How many numbers in this interval are coprime with y?

Return a int[] with N elements: for each valid i, the answer to the query given by X[i] and Y[i].

Notes

The values in Y are guaranteed to have a special form, as described by the last constraint. (Note that the problem can also be solved without this constraint.)

Constraints

N will be between 1 and 500, inclusive.
X will have exactly N elements.
Y will have exactly N elements.
All numbers in X and Y will be positive.
For each valid i, Y[i] will be at most 10^7.
For each valid i, X[i] + Y[i] will be at most 10^18.
For each valid i, Y[i] will not be divisible by any prime greater than 10. (I.e., each Y[i] will have the form 2^a * 3^b * 5^c * 7^d, for some a, b, c, d >= 0.)

Examples

{5 , 3}
{3 , 7}
Returns: {2, 6 }

In the interval [5 , 7] : 5 and 7 are coprime with 3 In the interval [3 , 9] : 3 , 4 , 5 , 6 , 8 , 9 are coprime with 7

{10}
{15}
Returns: {8 }

In the interval [10 , 24] : 11 , 13 , 14 , 16 , 17 , 19 , 22 , 23 are coprime with 15.

{ 1345420919 , 1247962786 , 884137069 , 553502418 , 1170113999 , 560311518 , 70067468 , 1528999044 , 1976356384 , 240857476 , 1809045279 , 1751239438 , 1148323368 , 584980927 , 1819182013 , 66891293 , 799649385 , 213955499 , 1990566306 , 1284073819 , 1841446016 , 640640558 , 418696979 , 681917452 , 1441969814 , 384674836 , 197074147 , 1829286221 , 983823602 , 1220232107 , 283587506 , 181760873 , 320711244 , 1167724574 , 735263290 , 1490825243 , 1728036091 , 805330757 , 872340638 , 1556908826 , 1046188233 , 533902269 , 1160664616 , 47027952 , 1118883195 , 832362980 , 113919244 , 1918532579 , 1046318478 , 2104485549 , 1055122749 , 740280845 , 597642459 , 1473819727 , 1422198297 , 2039612272 , 1858494562 , 1619272443 , 1721414844 , 694834516 , 692020901 , 2005002349 , 876595388 , 1012732144 , 1025243274 , 1611858677 , 356073738 , 605795717 , 269705785 , 1228414376 , 15220894 , 1315894017 , 1762316644 , 1175885509 , 1362921969 , 733716190 , 2008248489 , 1476841212 , 504765120 , 907083318 , 1433843113 , 1559887869 , 1647364163 , 2031485571 , 886223947 , 922078811 , 1923614194 , 597234861 , 393867605 , 1497545389 , 1292069376 , 1085888505 , 1355064090 , 21181115 , 2098620648 , 232823715 , 1633039791 , 307210738 , 838619431 , 1902745575 , 1535625113 , 853840325 , 1071155944 , 1150458108 , 2029725833 , 286594264 , 1884174297 , 1890490673 , 1763435475 , 241455768 , 650090343 , 1049794939 , 1801343636 , 149970857 , 933796861 , 540083935 , 1072049667 , 709927406 , 1137318795 , 1465917271 , 59989147 , 281904522 , 404322127 , 1415053236 , 303085636 , 355459126 , 1647876950 , 1936125426 , 662669863 , 339012733 , 1691387352 , 50811327 , 1192853057 , 615059647 , 1201269434 , 1075095241 , 901653910 , 937960082 , 818102266 , 517605737 , 1179415850 , 1468192608 , 1567400675 , 833275837 , 1618163464 , 353713888 , 1373359771 , 542729482 , 1063641293 , 363194917 , 2008646752 , 1123630439 , 645099438 , 265485230 , 391200026 , 948185073 , 620944355 , 2039076976 , 736826850 , 1283614218 , 230606060 , 280730554 , 1334425544 , 1423459116 , 895790200 , 388211330 , 351070708 , 1797444110 , 1326171411 , 1169172973 , 167566198 , 358103612 , 489881932 , 1734966872 , 1191379449 , 2108045395 , 2088680759 , 417255571 , 503291228 , 1004838404 , 780450488 , 364454331 , 2128468842 , 1425549925 , 629939560 , 372185220 , 226251350 , 1250883915 , 263778547 , 963078199 , 387014484 , 494384606 , 1243808752 , 1721440027 , 1917843721 , 2139598952 , 2109651356 , 121430780 , 1789559413 , 1288339119 , 1290603753 , 1957125610 , 1646442730 , 1780485684 , 1544608833 , 690338530 , 1741047431 , 1485805944 , 1107594101 , 96855010 , 343160699 , 1888044588 , 461309341 , 324145892 , 1166110864 , 1091248900 , 696331111 , 1392362213 , 194649166 , 960109657 , 207956764 , 581663649 , 1454494262 , 1451765515 , 155620028 , 1224854334 , 1443880818 , 117787735 , 1346285114 , 1085956582 , 1406126853 , 489405218 , 895598543 , 905085935 , 122407253 , 292723728 , 1595424464 , 1863454683 , 1778529671 , 555534916 , 1960309693 , 2121690369 , 296095855 , 274135385 , 298352612 , 1462206719 , 1365384284 , 994683723 , 707085283 , 1560033450 , 1954793379 , 915042046 , 2141697098 , 1261803993 , 219323913 , 149833477 , 339174678 , 1663204730 , 267621212 , 1685459791 , 601677664 , 1673748064 , 27381360 , 1497276206 , 431350350 , 149788613 , 1789999933 , 2026774814 , 2013243295 , 1421045955 , 434826081 , 1826069339 , 1395252675 , 730921936 , 2100204723 , 1693605287 , 45645006 , 1318105359 , 540805361 , 752730288 , 730655160 , 348115091 , 1667772334 , 724868609 , 1609919083 , 1887096246 , 874702086 , 1949093761 , 1402817327 , 1142323297 , 1487069903 , 2004494990 , 668587712 , 1514451263 , 1354287548 , 1099938062 , 1664239875 , 996803832 , 979229227 , 1529999521 , 270366139 , 1414055307 , 1208585212 , 1665618813 , 2144977242 , 1161306286 , 1211740451 , 43138599 , 331927996 , 1752545811 , 795868887 , 1062583155 , 2100660902 , 316157572 , 1787451764 , 1563096336 , 55770169 , 514670201 , 1364706448 , 1458587495 , 1656993497 , 704292703 , 1315598837 , 178097560 , 71260317 , 522402736 , 1278035621 , 1735500191 , 1519206567 , 109781199 , 1118016063 , 1789572705 , 1523836506 , 179117626 , 1307707870 , 1521330099 , 1340423912 , 371964672 , 1564468698 , 1672351907 , 2124510483 , 212853936 , 587451414 , 2077687736 , 529011507 , 227419529 , 1493300423 , 584781675 , 742089729 , 710523223 , 2043369169 , 251599577 , 1414815925 , 1211484357 , 429697136 , 1486076241 , 1733887092 , 1707732757 , 1074092783 , 1105610011 , 1817513955 , 44625197 , 747699067 , 1193866812 , 223742823 , 2055406936 , 567713263 , 1564166734 , 279887960 , 2132181960 , 1089034992 , 256914794 , 197552247 , 1676486405 , 187118881 , 726563753 , 1903905933 , 1680419303 , 1311345427 , 498512013 , 243458877 , 1207230947 , 750111589 , 1658274801 , 271231656 , 1179808725 , 996867393 , 2005118747 , 740057833 , 2070960175 , 963245109 , 410088139 , 2115585372 , 1710944176 , 1603954951 , 191844546 , 1618867463 , 24184565 , 1756011279 , 1898755422 , 8882876 , 697562622 , 8186567 , 206435122 , 226565379 , 195305447 , 932998874 , 2130471311 , 1875724750 , 96860652 , 481499676 , 2119183626 , 1304091598 , 1231611264 , 1629974779 , 1575323253 , 263936340 , 479358523 , 1432958352 , 1003994172 , 402835050 , 248719812 , 1414082311 , 370936773 , 1959663987 , 870553613 , 562781318 , 1431047802 , 894738177 , 171308948 , 1182319575 , 903621052 }
{ 4609920 , 583443 , 246960 , 218750 , 857304 , 605052 , 179200 , 3763200 , 105000 , 4320000 , 336000 , 248832 , 2571912 , 1344000 , 470400 , 4961250 , 588 , 74088 , 2250423 , 43218 , 3087 , 56448 , 1032192 , 128625 , 30 , 480200 , 7558272 , 2362500 , 3500 , 686 , 3375 , 8000000 , 874800 , 2755620 , 960400 , 168070 , 537600 , 8398080 , 14400 , 980 , 168 , 4941258 , 430080 , 3024000 , 480000 , 20412 , 4960116 , 3176523 , 491520 , 893025 , 160 , 1037232 , 1620 , 4900000 , 7558272 , 100352 , 129600 , 4096 , 500 , 1882384 , 12544 , 193536 , 1382400 , 8823675 , 6804 , 29160 , 128625 , 5443200 , 259200 , 2823576 , 7526400 , 329280 , 4667544 , 1500282 , 328125 , 118125 , 4725000 , 81920 , 3969 , 125000 , 3780 , 168070 , 12960 , 17920 , 373248 , 3920 , 2667168 , 336 , 30870 , 144 , 2370816 , 212625 , 245000 , 1050000 , 164025 , 3280500 , 4064256 , 7812500 , 1555848 , 408240 , 2074464 , 4251528 , 6722800 , 750141 , 437400 , 1036800 , 4608 , 816480 , 6146560 , 388800 , 6291456 , 30 , 1176 , 1372 , 295245 , 2952450 , 262144 , 241920 , 3675000 , 1451520 , 302526 , 2917215 , 58320 , 4704000 , 145152 , 5468750 , 5040000 , 240100 , 4134375 , 2755620 , 5600000 , 2916000 , 933120 , 210 , 705600 , 72030 , 1270080 , 5971968 , 4862025 , 2880000 , 145800 , 2857680 , 2 , 1587600 , 980 , 1640625 , 268912 , 453600 , 1458 , 30000 , 153125 , 560000 , 26880 , 1372000 , 1003520 , 889056 , 571536 , 350000 , 9289728 , 864360 , 303750 , 2688 , 109350 , 70 , 5625 , 5314410 , 87480 , 9447840 , 9843750 , 11250 , 2667168 , 141120 , 9375 , 9003750 , 56 , 344064 , 1428840 , 1680700 , 7348320 , 2296350 , 5400 , 643125 , 385875 , 125440 , 11907 , 675 , 6720000 , 6531840 , 2580480 , 6193152 , 444528 , 14112 , 9843750 , 420 , 276480 , 145800 , 8505 , 2500470 , 127575 , 7938 , 6048 , 100352 , 510300 , 588000 , 78732 , 2700000 , 8573040 , 7656250 , 254016 , 6300 , 6048000 , 3176523 , 1613472 , 148176 , 4536 , 882 , 250000 , 256 , 8820000 , 193536 , 12250 , 1889568 , 819200 , 216000 , 2460375 , 9447840 , 2822400 , 5529600 , 8067360 , 112000 , 126 , 96040 , 1536000 , 2823576 , 4390400 , 17010 , 2508800 , 250 , 6048 , 190512 , 221184 , 48020 , 10584 , 76545 , 1209600 , 61236 , 147000 , 51030 , 734832 , 826875 , 1500282 , 2211840 , 455625 , 327680 , 127575 , 337500 , 294000 , 112000 , 107520 , 1210104 , 1638400 , 960000 , 12544 , 765450 , 884736 , 35840 , 2571912 , 702464 , 55566 , 3087 , 10240 , 6322176 , 1029000 , 96768 , 21504 , 25088 , 4251528 , 3500658 , 2151296 , 1143072 , 992250 , 150000 , 781250 , 1344 , 3732480 , 6193152 , 607500 , 396900 , 33075 , 1764 , 98415 , 5832 , 6174000 , 472392 , 6588344 , 2100875 , 2381400 , 5760000 , 432180 , 32400 , 28350 , 1372000 , 6480 , 3937500 , 17150 , 117649 , 162 , 72 , 153090 , 2521050 , 4961250 , 7971615 , 108864 , 250880 , 47250 , 6250 , 92160 , 49 , 4375000 , 3225600 , 108045 , 194481 , 7350 , 31360 , 5467500 , 686 , 11907 , 1080450 , 7558272 , 1433600 , 4321800 , 10935 , 62500 , 20736 , 8960000 , 396900 , 3073280 , 35721 , 2278125 , 6125 , 23040 , 907578 , 1792 , 672280 , 30240 , 893025 , 6220800 , 688905 , 980000 , 8605184 , 752640 , 6635520 , 141750 , 1929375 , 175000 , 32928 , 9072000 , 3161088 , 1050 , 9261 , 259200 , 6144 , 735000 , 7257600 , 112500 , 2834352 , 1333584 , 3087 , 9680832 , 960400 , 34020 , 20412 , 207360 , 756000 , 8573040 , 1204224 , 5120 , 5250000 , 196830 , 2160900 , 4423680 , 7441875 , 4961250 , 18000 , 5040000 , 34560 , 1536640 , 1323 , 30 , 2322432 , 30625 , 1600000 , 2016 , 3111696 , 4199040 , 259308 , 640000 , 368640 , 2809856 , 2800000 , 59535 , 28672 , 16464 , 1680700 , 3096576 , 9216 , 600250 , 5600 , 43904 , 6422528 , 4478976 , 100000 , 1600 , 7112448 , 564480 , 13500 , 215040 , 219520 , 40500 , 1389150 , 141120 , 409600 , 78732 , 317520 , 425250 , 148176 , 5000940 , 35840 , 588 , 4705960 , 9604000 , 107163  }
Returns: {1053696, 333396, 56448, 75000, 244944, 172872, 61440, 860160, 24000, 1152000, 76800, 82944, 734832, 307200, 107520, 1134000, 168, 21168, 1285956, 12348, 1764, 16128, 294912, 58800, 8, 164640, 2519424, 540000, 1200, 294, 1800, 3200000, 233280, 629856, 329280, 57624, 122880, 2239488, 3840, 336, 48, 1411788, 98304, 691200, 128000, 5832, 1417176, 1815156, 131072, 408240, 64, 296352, 432, 1680000, 2519424, 43008, 34560, 2048, 200, 806736, 5376, 55296, 368640, 4033680, 1944, 7776, 58800, 1244160, 69120, 806736, 1720320, 75264, 1333584, 428652, 150000, 54000, 1080000, 32768, 2268, 50000, 864, 57624, 3456, 6144, 124416, 1344, 762048, 96, 7056, 48, 677376, 97200, 84000, 240000, 87480, 874800, 1161216, 3125000, 444528, 93312, 592704, 1417176, 2304960, 428652, 116640, 276480, 1536, 186624, 2107392, 103680, 2097152, 8, 336, 588, 157464, 787320, 131072, 55296, 840000, 331776, 86436, 1333584, 15552, 1075200, 41472, 1875000, 1152000, 82320, 1890000, 629856, 1920000, 777600, 248832, 48, 161280, 16464, 290304, 1990656, 2222640, 768000, 38880, 653184, 1, 362880, 336, 750000, 115248, 103680, 486, 8000, 105000, 192000, 6144, 470400, 344064, 254016, 163296, 120000, 2654208, 197568, 81000, 768, 29160, 24, 3000, 1417176, 23328, 2519424, 2250000, 3000, 762048, 32256, 5000, 2058000, 24, 98304, 326592, 576240, 1679616, 524880, 1440, 294000, 176400, 43008, 6804, 360, 1536000, 1492992, 589824, 1769472, 127008, 4032, 2250000, 96, 73728, 38880, 3888, 571536, 58320, 2268, 1728, 43008, 116640, 134400, 26244, 720000, 1959552, 2625000, 72576, 1440, 1382400, 1815156, 460992, 42336, 1296, 252, 100000, 128, 2016000, 55296, 4200, 629856, 327680, 57600, 1312200, 2519424, 645120, 1474560, 1843968, 38400, 36, 32928, 409600, 806736, 1505280, 3888, 860160, 100, 1728, 54432, 73728, 16464, 3024, 34992, 276480, 17496, 33600, 11664, 209952, 378000, 428652, 589824, 243000, 131072, 58320, 90000, 67200, 38400, 24576, 345744, 655360, 256000, 5376, 174960, 294912, 12288, 734832, 301056, 15876, 1764, 4096, 1806336, 235200, 27648, 6144, 10752, 1417176, 1000188, 921984, 326592, 226800, 40000, 312500, 384, 995328, 1769472, 162000, 90720, 15120, 504, 52488, 1944, 1411200, 157464, 2823576, 1440600, 544320, 1536000, 98784, 8640, 6480, 470400, 1728, 900000, 5880, 100842, 54, 24, 34992, 576240, 1134000, 4251528, 31104, 86016, 10800, 2500, 24576, 42, 1500000, 737280, 49392, 111132, 1680, 10752, 1458000, 294, 6804, 246960, 2519424, 491520, 987840, 5832, 25000, 6912, 3072000, 90720, 1053696, 20412, 1215000, 4200, 6144, 259308, 768, 230496, 6912, 408240, 1658880, 314928, 336000, 3687936, 172032, 1769472, 32400, 882000, 60000, 9408, 2073600, 903168, 240, 5292, 69120, 2048, 168000, 1658880, 30000, 944784, 381024, 1764, 2765952, 329280, 7776, 5832, 55296, 172800, 1959552, 344064, 2048, 1200000, 52488, 493920, 1179648, 3402000, 1134000, 4800, 1152000, 9216, 526848, 756, 8, 663552, 21000, 640000, 576, 889056, 1119744, 74088, 256000, 98304, 1204224, 960000, 27216, 12288, 4704, 576240, 884736, 3072, 205800, 1920, 18816, 2752512, 1492992, 40000, 640, 2032128, 129024, 3600, 49152, 75264, 10800, 317520, 32256, 163840, 26244, 72576, 97200, 42336, 1143072, 12288, 168, 1613472, 3292800, 61236 }

{ 1830360806 , 1316494453 , 1309264747 , 177508789 , 926524995 , 1144235348 , 262153599 , 1285837123 , 915150101 , 631538771 , 1987253008 , 1258547149 , 998236654 , 1592113144 , 1830370110 , 137410573 , 1404724516 , 1238555582 , 1102504107 , 1259197336 , 1304617958 , 1011814583 , 1573925044 , 1761659122 , 291029812 , 457238936 , 802674140 , 1850809329 , 1935355928 , 3420838 , 1256416788 , 1618233085 , 1319915290 , 418197887 , 1795741873 , 98956636 , 1562433234 , 2057895471 , 1384793758 , 330099686 , 541950594 , 1224563118 , 1588646834 , 1540187247 , 669192613 , 1271533296 , 1677597819 , 2073917128 , 362605229 , 632618278 , 1185630815 , 1667223186 , 1644432860 , 612072211 , 1281398660 , 1935462671 , 1069311146 , 2084072799 , 1638788351 , 857183425 , 2087493636 , 747721491 , 327932861 , 1259925277 , 1165919377 , 2123674734 , 1358881912 , 580868962 , 2034086556 , 596192021 , 910968647 , 428553501 , 1820755138 , 352131832 , 1968740747 , 342464103 , 1623665127 , 1498854918 , 268897582 , 1986270356 , 2131473195 , 1454528397 , 1506009893 , 1628422406 , 2066600607 , 639924904 , 1416401429 , 988428104 , 576514054 , 907706131 , 1845611528 , 516524041 , 1655427621 , 26060740 , 1776449317 , 673863349 , 2251825 , 987847580 , 1254732310 , 2036338381 , 1584039601 , 18217308 , 317408233 , 1257311090 , 370349140 , 138665332 , 1599775192 }
{ 25725 , 8168202 , 3430 , 655360 , 900 , 5040000 , 2074464 , 777924 , 2074464 , 414720 , 3037500 , 8823675 , 4214784 , 1555848 , 1215 , 294912 , 197568 , 4408992 , 3556224 , 12544 , 43008 , 787500 , 1715 , 3188646 , 28000 , 567000 , 147000 , 3136 , 480 , 103680 , 648 , 490000 , 63000 , 204800 , 47250 , 907578 , 463050 , 8268750 , 156800 , 17640 , 1646400 , 6174 , 212625 , 490000 , 3440640 , 2025000 , 10290 , 245000 , 3025260 , 8100000 , 937500 , 43008 , 562500 , 6002500 , 150 , 8437500 , 235298 , 1200500 , 78750 , 352800 , 7620480 , 980000 , 15309 , 362880 , 9144576 , 307200 , 52920 , 393750 , 1312200 , 1323000 , 5880000 , 75600 , 2985984 , 592704 , 125 , 3375000 , 27440 , 15552 , 20160 , 9375000 , 163840 , 42 , 34992 , 5598720 , 6353046 , 492075 , 1536 , 92160 , 127575 , 178605 , 2 , 600000 , 8470728 , 15309 , 24300 , 14700 , 4782969 , 428750 , 5512500 , 441000 , 3600 , 3061800 , 35 , 5376000 , 67500 , 243 , 5927040  }
Returns: {11760, 2333772, 1176, 262144, 240, 1152000, 592704, 222264, 592704, 110592, 810000, 4033680, 1204224, 444528, 648, 98304, 56448, 1259712, 1016064, 5376, 12288, 180000, 1176, 1062882, 9600, 129600, 33600, 1344, 128, 27648, 216, 168000, 14400, 81920, 10800, 259308, 105840, 1890000, 53760, 4032, 376320, 1764, 97200, 168000, 786432, 540000, 2352, 84000, 691488, 2160000, 250000, 12288, 150000, 2058000, 40, 2250000, 100842, 411600, 18000, 80640, 1741824, 336000, 8748, 82944, 2612736, 81920, 12096, 90000, 349920, 302400, 1344000, 17280, 995328, 169344, 100, 900000, 9408, 5184, 4608, 2500000, 65536, 12, 11664, 1492992, 1815156, 262440, 512, 24576, 58320, 81648, 1, 160000, 2420208, 8748, 6480, 3360, 3188646, 147000, 1260000, 100800, 960, 699840, 24, 1228800, 18000, 162, 1354752 }

{ 753727441 , 67418400 , 1786526780 , 95965797 , 183050299 , 293059788 , 1480371459 , 1388649712 , 681027775 , 1557338619 , 788689366 , 89570766 , 1807183721 , 749511052 , 2126566273 , 886293998 , 651279564 , 988810693 , 2046003039 , 1947028648 , 211011598 , 1707684759 , 1706565543 , 811615156 , 1455753630 , 752869452 , 778052373 , 239909892 , 695850656 , 1788078001 , 683211299 , 1449578096 , 1855496401 , 322254430 , 1545543892 , 2038546699 , 615314217 , 878431702 , 1279712763 , 1296341991 , 288286672 , 2068402128 , 1385912757 , 2095470392 , 670429532 , 1364995381 , 834280742 , 1321709095 , 206322426 , 732800132 , 1121254094 , 417334023 , 293001243 , 680335989 , 1228949179 , 1748754872 , 1433205440 , 2007001551 , 1988664763 , 2129056095 , 1647595903 , 524392414 , 1431150542 , 1355608655 , 846646843 , 829210785 , 1246671706 , 1461961060 , 1707642486 , 378900820 , 610819402 , 1995929158 , 299819299 , 1996732158 , 1943915901 , 970248830 , 1214243891 , 630712994 , 144474277 , 1420566316 , 1363513126 , 1265728370 , 1837900338 , 1656514368 , 1946064358 , 919365868 , 1257785591 , 1231786150 , 778883770 , 1098966706 , 1213358596 , 278996025 , 1623359119 , 497025490 , 1634604679 , 322522313 , 1326236274 , 733792736 , 1784483372 , 886395112 , 1112693555 , 247819126 , 734840621 , 1412512854 , 97067635 , 531272873 , 235278035 , 1311311525 , 1161985867 , 379752311 , 584394192 , 378015344 , 1645480681 , 274810882 , 2034529711 , 1444061390 , 1194176749 , 1144831653 , 528363891 , 1973060519 , 96314710 , 1741722487 , 104572895 , 1719673828 , 91264328 , 1739177573 , 2042196141 , 1417500601 , 325486661 , 1679195864 , 156412064 , 1438180215 , 1927014989 , 891252684 , 703209420 , 2024082624 , 1422525557 , 938487455 , 1187910500 , 437027775 , 1318239765 , 1772304692 , 815043118 , 816236797 , 2047115573 , 702089180 , 112814539 , 1093808673 , 1846920832 , 641178429 , 919385543 , 1943235542 , 235417267 , 1023958437 , 1515425721 , 326681594 , 615652362 , 1410138213 , 1744182195 , 941139022 , 941850429 , 1900594258 , 231835588 , 721381769 , 644363294 , 935045008 , 597980744 , 2066888850 , 1873532462 , 1785891244 , 356432976 , 1044288578 , 1410712287 , 1171476093 , 1860525375 , 1310344211 , 1873565272 , 1973339913 , 256669235 , 1573002455 , 467034693 , 1176054778 , 1368754348 , 702451960 , 52529566 , 736696421 , 1029133553 , 668181927 , 2146834633 , 625832099 , 1609320948 , 941201413 , 378942709 , 1841156536 , 1662583182 , 1023306002 , 628717895 , 113080277 , 942711203 , 354766708 , 1898971520 , 1299144178 , 1399055285 , 1162200158 , 323136622 , 1112097011 , 325060720 , 49218245 , 937953275 , 581729955 , 1622220699 , 1404987968 , 1757784732 , 843491399 , 2107439927 , 1810314297 , 1580187819 , 989089831 , 331012576 , 1579538803 , 1614921930 , 1940333523 , 373256568 , 1993864638 , 1634006410 , 2035839749 , 869686991 , 115240656 , 1436377 , 1812398193 , 470007363 , 1900407897 , 964058722 , 1869062648 , 915124406 , 1287195343 , 833676010 , 1240185126 , 1336413587 , 1771629285 , 1821915080 , 811150637 , 1029133604 , 1432216163 , 1654642035 , 989089882 , 1095046811 , 1087346205 , 1978179712 , 1426059386 , 519401360 , 1445617993 , 1218909261 , 892657927 , 1291998982 , 705432022 , 781014027 , 14202324 , 820672678 , 782450403 , 1826600516 , 1290680040 , 535374651 , 643175589 , 1012259039 , 1450499057 , 1930370931 , 1845935049 , 543200534 , 1119300869 , 1470080685 , 217631965 , 1930451506 , 351730640 , 1649848127 , 1437609892 , 1340820521 , 597411289 , 377472449 , 1171516584 , 2023470675 , 896873808 , 469650929 , 1094896287 , 1789531734 , 1761649910 , 1800328308 , 423062112 , 1775852234 , 473517337 , 1205512514 , 1454969101 , 1764197377 , 1740887165 , 2098144690 , 628972767 , 1043902573 , 1881031972 , 327424167 , 1587103106 , 852849193 , 1797504851 , 1804735070 , 635817050 , 1751842 , 1307099548 , 2073426941 , 1342572362 , 1904510836 , 303415741 , 366605298 , 1780497862 , 1200289548 , 836256226 , 727910500 , 842337633 , 450422487 , 380755160 , 1265399744 , 78791072 , 854272496 , 323428610 , 1533760173 , 470986224 , 2064315774 , 1484421214 , 1099958991 , 960734698 , 1217969537 , 1427383157 , 400354155 , 2070818729 , 1077404360 , 57605576 , 559152130 , 1079156201 , 1364705123 , 485095423 , 274244915 , 1121732310 , 788511163 , 640850212 , 754746524 , 1988800711 , 1477106437 , 1482657023 , 683654695 , 1927528923 , 1863412182 , 1949054439 , 2006319995 , 570201030 , 124999400 , 1392596519 , 1041187253 , 41831525 , 729534084 , 2141146243 , 1002566222 , 1947503620 , 1421045752 , 1402920376 , 1870838701 , 350966463 , 1460525951 , 282507182 , 1430122663 , 677747425 , 767602604 , 1704367577 , 1799479734 , 1556113767 , 197734140 , 406742609 , 1397430829 , 1674840576 , 1889399632 , 2081085523 , 1454885851 , 1605328165 , 1882656313 , 1313722197 , 28045546 , 2007655712 , 558835067 , 1069232799 , 2049487236 , 1288369150 , 1062895393 , 904569809 , 1088389121 , 336457496 , 160006536 , 811744173 , 687423958 , 1620532486 , 1094251355 , 2117546621 , 150796262 , 1861853958 , 1674430549 , 1950275996 , 1270484076 , 1872164689 , 209534956 , 520431256 , 1399521616 }
{ 2612736 , 350 , 17010 , 1741824 , 57344 , 1250 , 5878656 , 3572100 , 6480000 , 15120 , 435456 , 917504 , 1620 , 781250 , 36750 , 110250 , 9882516 , 716800 , 5904900 , 900375 , 2949120 , 756000 , 5184 , 338688 , 23520 , 8605184 , 7000000 , 1769472 , 3430 , 388800 , 207360 , 1701 , 2540160 , 937500 , 9450000 , 35 , 5760000 , 5488000 , 3781575 , 3543750 , 729 , 595350 , 1120000 , 163840 , 1372 , 1600 , 7290000 , 84000 , 1250000 , 4147200 , 5598720 , 192000 , 171500 , 15 , 1080 , 3932160 , 8823675 , 9646875 , 2359296 , 91125 , 1920000 , 137200 , 205800 , 279936 , 11760 , 182250 , 306250 , 567 , 476280 , 428750 , 1620 , 3241350 , 9834496 , 6806835 , 8640 , 1215 , 9920232 , 92610 , 174960 , 4862025 , 168000 , 470596 , 411600 , 9031680 , 492075 , 691488 , 147 , 2058000 , 2976750 , 9261000 , 49 , 351232 , 114688 , 1389150 , 3969 , 508032 , 98 , 3292800 , 3292800 , 555660 , 48020 , 2520 , 70560 , 46080 , 54 , 1720320 , 800000 , 40000 , 28125 , 12150 , 112000 , 1008000 , 1555848 , 3750000 , 864360 , 188160 , 903168 , 1036800 , 96000 , 121500 , 918540 , 110250 , 3500658 , 8000 , 21870 , 6912 , 1433600 , 29400 , 6858432 , 279936 , 8573040 , 15120 , 2809856 , 472500 , 1658880 , 4 , 11025 , 373248 , 40500 , 185220 , 1280000 , 918540 , 8847360 , 588000 , 1181250 , 3189375 , 6200145 , 18225 , 1102500 , 344064 , 653184 , 15876 , 54 , 786432 , 108045 , 27216 , 1968300 , 22500 , 314928 , 4705960 , 5145000 , 1399680 , 48600 , 1210104 , 6000 , 7077888 , 1224720 , 72000 , 196000 , 2800 , 6378750 , 41160 , 1764735 , 4050 , 2976750 , 625000 , 5882450 , 6096384 , 2257920 , 497664 , 131250 , 439040 , 6531840 , 153090 , 294 , 414720 , 3889620 , 8429568 , 1771875 , 43904 , 3888000 , 708588 , 5927040 , 1260 , 207360 , 46080 , 33600 , 49 , 746496 , 4840416 , 3888 , 1905120 , 2940 , 108 , 3687936 , 2688 , 735000 , 7024640 , 9797760 , 500000 , 1536000 , 900375 , 8957952 , 840000 , 12600 , 40320 , 56250 , 9219840 , 24300 , 15750 , 396900 , 45360 , 2362500 , 1020600 , 105000 , 138240 , 4741632 , 3483648 , 157464 , 1310720 , 1433600 , 2160000 , 96768 , 9001692 , 8437500 , 140000 , 1400 , 559872 , 564480 , 81000 , 36864 , 12005 , 5505024 , 338688 , 8470728 , 62500 , 1968750 , 35840 , 50400 , 6860 , 1518750 , 2458624 , 202500 , 177147 , 790272 , 7962624 , 8400000 , 235200 , 2625000 , 108045 , 55125 , 1224720 , 56000 , 984150 , 1050000 , 35280 , 13824 , 1715000 , 9112500 , 1882384 , 8857350 , 28125 , 2016 , 1920 , 6250000 , 600 , 156800 , 1048576 , 605052 , 5040000 , 2500000 , 235200 , 1008420 , 148176 , 3333960 , 186624 , 87808 , 9175040 , 3444525 , 65856 , 86436 , 800 , 6322176 , 3919104 , 5598720 , 524288 , 525 , 68040 , 235200 , 50000 , 8859375 , 1176490 , 2239488 , 73500 , 2016840 , 1190700 , 918750 , 972 , 25088 , 112896 , 10240 , 15120 , 2592000 , 2744000 , 691488 , 2880000 , 6250 , 1750 , 2560000 , 9720 , 161280 , 62208 , 336000 , 56448 , 2401 , 108000 , 24 , 172872 , 1185408 , 250880 , 1376256 , 4133430 , 180 , 137781 , 4480 , 8266860 , 8601600 , 7112448 , 46656 , 248832 , 50176 , 250880 , 4194304 , 7 , 216000 , 1050000 , 2917215 , 2963520 , 1786050 , 506250 , 6773760 , 61440 , 40 , 1062882 , 762048 , 3200 , 7056000 , 3499200 , 437400 , 3176523 , 312500 , 134400 , 4320000 , 2058000 , 7348320 , 15750 , 1594323 , 6400 , 3888 , 6722800 , 3265920 , 1120000 , 829440 , 1111320 , 1146880 , 8334900 , 21870 , 1080450 , 2361960 , 4116 , 2940 , 5468750 , 207360 , 3888 , 423360 , 14580 , 338688 , 1361367 , 8709120 , 10935 , 1433600 , 1411788 , 559872 , 425250 , 125440 , 1771470 , 5904900 , 35280 , 3889620 , 35721 , 9375 , 1012500 , 4593750 , 7938000 , 20250 , 351232 , 6553600 }
Returns: {746496, 120, 3888, 497664, 24576, 500, 1679616, 816480, 1728000, 3456, 124416, 393216, 432, 312500, 8400, 25200, 2823576, 245760, 1574640, 411600, 786432, 172800, 1728, 96768, 5376, 3687936, 2400000, 589824, 1176, 103680, 55296, 972, 580608, 250000, 2160000, 24, 1536000, 1881600, 1728720, 810000, 486, 136080, 384000, 65536, 588, 640, 1944000, 19200, 500000, 1105920, 1492992, 51200, 58800, 8, 288, 1048576, 4033680, 4410000, 786432, 48600, 512000, 47040, 47040, 93312, 2688, 48600, 105000, 324, 108864, 147000, 432, 740880, 4214784, 3111696, 2304, 648, 2834352, 21168, 46656, 2222640, 38400, 201684, 94080, 2064384, 262440, 197568, 84, 470400, 680400, 2116800, 42, 150528, 49152, 317520, 2268, 145152, 42, 752640, 752640, 127008, 16464, 576, 16128, 12288, 18, 393216, 320000, 16000, 15000, 3240, 38400, 230400, 444528, 1000000, 197568, 43008, 258048, 276480, 25600, 32400, 209952, 25200, 1000188, 3200, 5832, 2304, 491520, 6720, 1959552, 93312, 1959552, 3456, 1204224, 108000, 442368, 2, 5040, 124416, 10800, 42336, 512000, 209952, 2359296, 134400, 270000, 1458000, 2834352, 9720, 252000, 98304, 186624, 4536, 18, 262144, 49392, 7776, 524880, 6000, 104976, 1613472, 1176000, 373248, 12960, 345744, 1600, 2359296, 279936, 19200, 67200, 960, 1458000, 9408, 806736, 1080, 680400, 250000, 2016840, 1741824, 516096, 165888, 30000, 150528, 1492992, 34992, 84, 110592, 889056, 2408448, 810000, 18816, 1036800, 236196, 1354752, 288, 55296, 12288, 7680, 42, 248832, 1382976, 1296, 435456, 672, 36, 1053696, 768, 168000, 2408448, 2239488, 200000, 409600, 411600, 2985984, 192000, 2880, 9216, 15000, 2107392, 6480, 3600, 90720, 10368, 540000, 233280, 24000, 36864, 1354752, 995328, 52488, 524288, 491520, 576000, 27648, 2571912, 2250000, 48000, 480, 186624, 129024, 21600, 12288, 8232, 1572864, 96768, 2420208, 25000, 450000, 12288, 11520, 2352, 405000, 1053696, 54000, 118098, 225792, 2654208, 1920000, 53760, 600000, 49392, 25200, 279936, 19200, 262440, 240000, 8064, 4608, 588000, 2430000, 806736, 2361960, 15000, 576, 512, 2500000, 160, 53760, 524288, 172872, 1152000, 1000000, 53760, 230496, 42336, 762048, 62208, 37632, 3145728, 1574640, 18816, 24696, 320, 1806336, 1119744, 1492992, 262144, 240, 15552, 53760, 20000, 4050000, 403368, 746496, 16800, 460992, 272160, 210000, 324, 10752, 32256, 4096, 3456, 691200, 940800, 197568, 768000, 2500, 600, 1024000, 2592, 36864, 20736, 76800, 16128, 2058, 28800, 8, 49392, 338688, 86016, 393216, 944784, 48, 78732, 1536, 1889568, 1966080, 2032128, 15552, 82944, 21504, 86016, 2097152, 6, 57600, 240000, 1333584, 677376, 408240, 135000, 1548288, 16384, 16, 354294, 217728, 1280, 1612800, 933120, 116640, 1815156, 125000, 30720, 1152000, 470400, 1679616, 3600, 1062882, 2560, 1296, 2304960, 746496, 384000, 221184, 254016, 393216, 1905120, 5832, 246960, 629856, 1176, 672, 1875000, 55296, 1296, 96768, 3888, 96768, 777924, 1990656, 5832, 491520, 403368, 186624, 97200, 43008, 472392, 1574640, 8064, 889056, 20412, 5000, 270000, 1050000, 1814400, 5400, 150528, 2621440 }

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OneGcd with a public method vector<int> solve(vector<long long> X, vector<int> Y) · 31 test cases · 2 s / 256 MB per case