1 条题解
-
2
在原版做法的基础上，我们通过打表（或者查 OEIS A049048）可以发现，对应答案不为 的合数只有 个。于是我们可以先用 Miller-Rabin（选取 为底数判断三次）做素性判断，再对合数查表（查不到说明答案为 ）。该做法的时间复杂度为 。
#include <bits/stdc++.h> using namespace std; map<int, int> table; const string TABLE = R"( 996818003 12611 995994551 18704 993710489 22289 992943131 14343 992703487 663 992106239 22271 988778957 569 988516369 23455 988413071 13461 987936349 2549 986096173 623 985206779 17943 984991919 22191 984932411 6672 984182447 231 982099291 29031 981865057 12341 979930297 8721 979672979 22131 979075949 459 977182067 30647 977055251 11775 976379527 16001 974497049 29919 973838777 22065 973485749 22061 971192627 22035 970663829 22029 968730331 4215 968440373 25631 966110923 18519 965911127 21975 965586649 21879 961925693 741 961858081 881 961476421 10649 961406777 9179 959866573 3105 959708381 4086 958541219 21891 956463953 15401 954029303 5747 953768047 16425 953485543 17135 949033139 16475 948061739 21771 947676571 29151 946146749 21749 944967271 6299 944844191 22367 944059877 21725 943861543 17354 942383311 851 938045291 10091 938010583 6308 936390437 9465 936055027 15604 935786807 20403 933835589 8259 932256161 11120 931720627 12471 930987047 57 930730991 8441 930150787 12515 928430819 3431 927065443 11148 926119697 18057 924693509 21501 922600501 13061 921333713 27395 921159619 10863 918367691 17541 917707801 13870 915593227 3623 914626649 14085 914528011 128 912567781 10889 912567437 23369 910595237 265 909276689 21321 908563099 1996 906513667 9657 906239819 10372 905572897 4484 903009649 4740 902806277 21245 902330003 5571 900427867 16647 898639103 16475 895105489 16559 894766583 9753 891535217 10597 889147621 26249 887806123 7892 886426483 10430 882750719 22737 880203179 14230 879605317 19509 878513939 19721 875568413 3026 875508259 1603 872886451 5410 872470877 20885 871732241 1050 871692883 17517 870773413 1731 868507427 18948 868400983 16869 866877433 24849 863779591 17291 863322727 6055 862972739 20771 862806569 20769 862590767 22071 860720893 24681 860099561 19833 856146691 11015 853611337 8373 851949031 27939 849538357 12839 849433649 16695 846473519 25241 845472721 3977 845436167 1229 843001277 18403 841489573 8351 841012577 20505 838053329 17634 837944791 19425 837731669 3123 835771169 20441 835607639 20439 834739753 25799 834026429 13097 833569423 10935 833275249 21009 833156609 20409 831858241 17159 831712109 15425 829920607 97 828011543 25451 827890783 105 825353479 23079 824170859 12249 823875527 20295 823796879 8615 823597043 8251 823380133 14925 822764821 17319 822209137 4854 820933433 7295 818963569 2391 818772739 20518 818711911 4338 818526029 20229 817528709 1047 815202211 3494 814162127 20175 810842231 29 809669717 1607 808917127 12444 808777867 12149 808710667 1751 805879309 14745 804025049 20049 802913093 15049 802289941 17495 801620819 20019 801217199 1335 800213903 1037 799339049 1047 799229609 13889 799220189 19989 798117949 272 795906493 15 788859059 19859 788597393 4616 788518909 7079 787271039 19839 786109217 18537 785914121 18585 785340607 27959 785050499 19811 781919741 16296 780196993 13175 780144749 19749 774624479 19679 773910031 6381 773063521 7586 770606327 15491 769449011 401 768655729 483 768026027 19595 766964179 2367 765636427 585 765463793 15159 762623377 1317 762525427 26554 762249941 7565 759881257 27041 757558349 19461 756765661 16034 755358691 43 755286221 5145 754758377 19425 754535449 281 754292219 19419 753196589 191 752574983 7239 750036323 15677 748550039 10779 747917623 2163 747590189 10449 744475493 4480 744039983 2169 743373067 2696 742839239 19271 741987017 3385 740933813 2446 740405257 7157 738951989 15765 738669989 21011 736152727 3123 735344551 17441 734976409 2555 734695067 21267 734653961 915 733315753 9627 732371677 15887 732280823 5169 731301287 6909 730331513 18837 729235459 9885 728375419 4563 727405309 6671 727223323 21177 726662669 7602 726047129 24021 725970709 431 724101947 20895 723365177 676 721352603 329 721200427 25251 718646363 5236 717607529 3963 717565061 19539 717110587 2121 716726771 899 716352359 1191 715614421 155 715083893 16205 711517129 1750 711407783 9939 711056999 14138 710715233 20549 707006221 10611 706807721 15911 705846377 18785 705126073 11505 704688041 7346 702543869 18741 702159127 6365 701742607 14765 697558591 4109 697293041 8285 696231707 15629 694202573 10449 694080559 13645 694056617 3010 693917723 12192 693390673 25307 691504447 505 689312177 676 687742883 9596 687480877 10348 687389449 431 687065273 6027 685906163 6749 685188727 11184 684666509 18501 684413773 25069 683688023 11015 683668987 10449 681789571 10139 680823449 18449 679126043 2551 678785509 65 678543911 10695 676844027 18395 676657867 17181 676505737 9780 676154659 17541 676028083 3909 675547681 12639 674692541 23165 674656439 6908 674428891 832 672972499 19539 671854199 14765 670604531 5885 670254173 10863 670108487 1108 669798299 18299 669284773 22717 669033481 1516 668773877 18285 668693203 5957 668131349 3537 664046917 22227 661524203 9849 660737257 5005 658177133 1049 657988843 48 657556979 18131 657429281 10322 657205961 1533 657121877 18125 656073521 15371 654948527 18095 654759311 9717 653685889 7671 653501627 18075 652152811 7319 648796783 37 646922699 4364 644853827 17955 644852783 4131 644762917 20639 644143439 25347 642365149 2711 642270719 17919 642122077 13054 641051903 2129 639406679 17879 638607947 4361 638442713 2501 638093773 8698 638089303 8115 635768411 3051 632759359 6005 632298839 3677 632257211 4505 630976943 17181 630718483 1598 630481249 9717 629943103 18141 629858777 17745 629044769 2547 628353697 13107 628059319 21755 627447599 17711 627385397 6459 627325561 20847 624866653 16425 624291743 16785 623678359 2644 619368241 21699 617318881 12551 616350313 640 616022549 17549 615575089 272 615322459 6077 614771713 16925 613225061 4677 613220633 15953 612217913 15677 611378321 7751 611209073 2283 610313071 4300 608834069 4155 608776183 22191 608610917 2056 606170687 7219 605907559 4505 605876363 9677 605795543 5283 604086887 6766 601368539 17339 601130263 20591 599612443 5890 598648697 4612 598043819 17291 597891067 12965 597298157 7527 597119623 21557 596881777 8037 596145367 2108 593637749 3033 592469321 19062 591977849 14387 590039063 1421 589527349 15669 589127743 5333 587139221 8561 586476377 19137 586022167 10461 585932027 17115 584290019 17091 582707407 8465 582273827 19839 579022243 15906 578993537 13737 578697209 17009 578460679 12123 578375593 16013 576336031 14523 575946187 90 575435849 16961 574472273 2241 572995877 16925 572760913 14049 572448101 1335 571393007 16551 571342507 3299 570732047 401 569210669 16869 567155417 841 566897567 15642 565997921 6269 565895851 570 565169009 16809 564400267 3907 562938011 905 561341323 5705 560732021 1520 560471939 16739 559715291 4722 559548097 22077 558751133 1705 558202961 2547 558051671 2241 557930309 16701 557340989 1431 557061737 1319 556869853 3021 556731391 3040 556378861 15573 556368721 111 555927839 16671 555468259 9389 551763833 4390 551545861 429 551535077 16605 551430961 12147 549881051 1457 548483759 16559 547258003 1425 546667477 13791 546639271 15119 544501961 7701 542092049 342 541835051 5865 540901717 12003 540556231 640 539690077 458 536755469 17495 536541371 19139 533741647 800 533149049 19246 529455413 6822 529181777 16265 529181671 5890 528361837 5003 527867869 12933 527837467 9226 526697453 15635 525872857 7505 525047461 8119 524012941 8595 523774747 15906 523730429 16181 522588133 431 519914669 11800 519474727 16935 518656559 16102 518178527 16095 518115947 12471 517253899 19007 517220449 13913 516998177 5705 516634439 16071 515393273 2349 513522881 170 511882453 1577 511553501 1705 509751577 1731 506428253 5304 506201489 249 505623553 2004 504745877 15885 504509321 17541 503843357 14840 503623843 11167 503405849 11431 503374909 7295 500735659 629 500687189 15821 500578873 8318 497769133 6381 497477389 46 497168879 14141 497149277 15765 495695423 6567 495530033 16059 495393541 6280 495303269 21339 494258801 2549 493423247 4565 492781123 13839 491249783 10845 490992197 12341 490486859 15659 487876579 5333 487721257 56 487546459 12201 487067117 3265 486630211 6097 486129617 2381 484963513 10449 484934377 12977 484537517 4215 483508499 3257 483274423 6489 481886623 18411 480777953 21801 480489179 3519 480135343 19569 479638529 165 477950747 11699 477827071 5246 477604847 10449 476693807 13755 476631301 13439 476465993 6446 476298709 17979 475938377 15425 475930313 9947 474268667 3518 473227229 15381 471321287 1521 471286687 11914 470159101 10065 469767863 8229 469258547 14841 469092361 10091 468331301 5857 466884139 4360 466627279 13763 465359431 10091 464198773 8835 463910731 1949 462952907 7586 462941429 9065 462760471 7586 462562921 8055 462019001 6201 461685691 3732 460064551 8442 459666359 15159 459343397 10909 459335717 43 458212127 15135 457848929 15129 457241509 11525 456797167 15875 456397577 15105 456381763 11397 453080527 7605 451448093 11375 450996373 875 450580301 6672 449629799 11441 449024539 4809 448785811 13995 448174421 597 446791253 11645 445453201 5035 445181831 1705 444165677 10857 443497679 10449 440584769 14841 438630559 503 437720747 6609 437694823 4701 435349643 7175 435028229 13715 432900599 14711 432536563 148 432329089 10372 432071051 11055 432007721 4722 431927261 17291 431658949 971 430987793 8705 429413731 5068 429376859 14651 428486699 5957 425750789 14589 425683933 6114 425599973 4279 425004137 8627 424818803 12839 424523233 5379 424118249 14561 423233803 1229 422510399 1577 422372579 14531 421572601 10251 421501123 45 419830871 105 419068823 63 417579037 8613 417231907 5536 416841881 10935 416002589 14421 415896493 15425 415594537 9417 415490021 8770 414232127 6351 413578651 431 412135891 12249 411740863 4935 410551111 7295 410253689 14321 408728069 15272 406664927 272 406662097 2129 406360763 10485 405602741 9478 404431019 14219 404414891 13181 403635077 14205 402549223 10955 401932127 14175 401915273 636 401138299 2056 399942233 7042 397446901 429 396610763 1451 395760437 4531 395202023 4353 395156327 14055 394819049 14049 394068709 19581 393863383 9370 393784871 5301 393030179 10372 392574209 14009 392550497 1289 392468459 6371 389084833 9995 388371493 18491 388101001 3999 387481091 6671 387476911 18915 387462233 11240 387287167 11769 386545109 13901 386433899 13899 386096747 13203 385277153 16367 385100627 13875 384989453 878 384878639 13871 383651137 18209 382769767 15159 381428219 308 381268933 4924 381225077 13805 380180117 1971 379469411 6648 379185377 12399 378986891 2037 377900891 180 377806687 9717 377406083 721 376599131 1601 376361933 3669 376212359 4142 375212027 7594 374327101 10779 374309759 9125 373494487 14577 373186357 4257 370909243 5396 369888781 5238 369716027 13595 369389789 13589 367915963 3019 367326959 13551 367054333 18215 366566311 13298 365876089 5855 365702489 13521 365349067 2814 365018603 6843 364649189 3389 364372661 3819 363218627 13475 361258727 155 360888133 2849 360867889 4573 360772067 17921 360206219 13419 360143293 1577 358062179 13379 357821077 14637 357419981 90 357242309 13727 355689343 9065 354096871 12917 353855329 7667 353630813 11465 352666603 1955 351747853 1127 349479209 9197 349338527 13215 349173197 12657 348222431 2870 347608237 894 346910969 13169 345899797 9057 344596877 13125 344517889 17681 343482143 10863 343337909 13101 341962711 855 341283331 15641 340386811 7757 340129739 3998 340118281 12407 339931807 13679 338117009 13001 337944281 676 337825193 5957 337439033 10131 336918551 465 336640823 18255 336558539 12971 336247277 12965 335521559 12951 334845883 141 333349109 12909 332214503 4917 332098573 4155 331876849 1327 331710011 2352 330381523 803 330360659 12851 329798779 4263 329744039 12839 329558917 1049 328853869 971 328820189 12821 328717619 12819 327933071 10319 327180989 12789 326405383 4259 326143229 7319 325165261 16347 324192311 3355 323202599 12711 322543453 4131 322479331 1619 322035281 676 321070469 12669 320751727 2129 320158859 12651 319103621 8115 318036809 12609 318016967 6141 317736773 4701 317268781 13757 316631141 17181 313008133 8203 312356659 4722 312012689 12489 311469217 335 311114039 12471 309021137 7407 308045887 5097 306590803 785 305960159 9329 304940393 2169 304859777 12345 304662269 12341 304411769 9869 303782497 321 303736583 2056 303721903 5219 303330191 10655 302498587 4279 300137249 12249 299663311 8717 299648627 7425 299544247 11321 299497901 1269 298980119 12965 298589779 9711 298180409 12209 297985553 5430 297630247 4660 297497027 12195 297264119 1577 296061011 119 296049269 2249 295683457 9197 295330843 1421 295133893 5890 293824171 12141 293736857 17045 293574131 6261 293413199 12111 293390899 6009 293121749 1643 293090389 9437 293079037 4103 290796133 1595 290323769 12741 289743721 3396 289454021 9831 289205647 5705 288560971 3369 288324887 3006 287478409 8291 287373607 4673 287340377 11985 287339693 13728 286716277 16475 286280123 6315 285853367 4395 285561091 2546 285139139 11939 284840123 11345 284699407 4791 283228277 9279 283184819 4791 283066669 6269 280004279 11831 279141281 2232 278571583 6567 278428093 431 278089169 8291 277772351 2765 277606187 9417 277130563 5716 276736049 429 275295931 2448 275197529 11729 274541027 11715 273916931 1425 273891869 2819 273781831 10329 273101321 243 272519089 4431 271078133 3249 270085313 6501 267732019 3185 266934301 2271 266359853 5705 265780321 9341 265281953 803 265091201 7947 264735377 11135 264603509 11501 263573351 8745 263175611 5559 261351163 9489 261211519 10161 260823763 570 260560897 4269 260452823 8405 259463587 5502 258796177 69 257995523 135 257109967 1255 256296119 11319 255847441 1556 255407069 8037 255373483 1889 254898827 4515 254816363 2209 254758877 11285 254681717 1597 254388191 13116 254163913 2379 254127239 11271 253343263 9489 253157227 15231 251739203 7295 251695957 7539 250889599 14319 250712027 11195 250255139 14751 249960059 4157 249638339 11171 249279683 8891 248906873 9495 248542799 9313 247916003 370 247866503 4019 247764929 11129 247437269 132 246699391 3465 245809877 11085 245509559 2327 245399491 1092 244481327 11055 244039277 11045 244021013 3519 243299711 4601 243147493 277 242925169 7409 242763877 6687 242099009 11001 241765847 5105 241341181 1541 241031177 1386 240780539 10971 240120889 7175 240073877 4466 239305579 54 239203127 10935 237718109 10901 237290203 13145 237228899 10527 236993363 6565 236167201 842 235219861 8177 234652987 14841 234615013 10305 234266729 476 234233827 8781 233281817 1837 232714301 10091 232427579 10779 232126471 1108 231221759 10751 230436317 3149 229590601 10005 229171751 429 227748029 92 227407717 6141 226997773 6344 225735421 8693 224985077 10605 222503773 12712 222275717 1655 221948609 917 221014799 10511 219763039 905 219596269 279 219022117 6710 217730687 718 217469267 935 217108217 69 216064837 11055 213510779 10331 213482197 4795 213015119 10319 212900269 7838 211430179 1207 210989549 8223 209007343 6027 208988789 10221 208316183 5562 207595519 1751 207387443 8729 207350509 67 207164977 6351 206656181 1801 206575751 10007 206542649 10161 205931809 2406 205905691 9963 205818461 12509 205030181 2031 204810493 5867 204604381 9677 203838463 8967 203783443 6999 203707019 10091 203474273 2129 203166169 2592 203127517 2159 202235609 1121 201111179 9731 200933461 9713 200905123 6051 200398343 401 200228393 1092 200204101 11241 200114653 189 198510313 1451 196902089 9921 196665289 12495 196160267 8915 195801481 293 194734213 1481 192877199 6710 192611669 760 192497153 3861 192168209 9801 191998199 7685 191561309 272 191306579 9779 191215901 2841 190234687 1971 190064551 9207 190016023 5055 189926333 11615 189433379 9731 188860559 8421 188658089 4481 187473269 6201 187185643 9125 186720553 2675 186640859 9659 185591479 6261 185513753 2101 185483429 9629 185267113 13395 184508707 9101 184465207 8121 183626293 3299 183067723 5975 182406331 7757 182405281 3389 182257879 3819 181656367 4722 181461473 1784 181252303 6867 180906821 2355 180710713 125 179918723 2254 179827603 6071 179486173 4722 179468417 8829 178957631 4335 177859229 9429 177482219 9419 177355193 8099 177175919 824 176804609 9401 175866653 2546 175085653 3200 174331127 9335 174011603 6710 173850241 10709 173508347 981 173419243 7808 173209627 10667 173031037 6561 172916407 10889 172484399 444 172154447 2339 171065399 5855 170796419 4439 170247377 9225 170026019 9219 169323503 709 169131247 5079 168365761 9785 167987399 924 167765987 2132 167673827 9155 166880881 3185 166808729 10787 166576877 9125 166346227 161 164553359 12761 163990369 10319 163957369 3299 162575057 3257 162128069 11381 162011873 1362 161989757 2415 161844649 2249 161263807 1949 160930769 8969 160643849 8961 159365707 9039 158919073 4701 157247879 12477 156461803 1731 155999147 417 155964241 9131 155946629 8829 154757789 2001 154631987 7586 154567711 7586 153483959 8759 153469733 2675 152917747 10241 152702917 8251 152644127 8735 151838083 2675 151537739 321 151211743 1619 151110419 8691 151028693 8037 150554627 8675 150460747 2244 149349611 4782 148883513 96 148036151 5849 147791027 8595 147665491 8361 147241379 8579 147218849 1417 146624249 8561 146027747 515 145950377 2143 143873687 1299 143649853 1383 143089123 8370 142645429 6689 142525751 5259 142471163 709 142110257 4860 141868589 8421 141160423 5415 140896237 1421 140655589 1376 138961507 2765 138959021 671 138747097 545 138320027 8315 137456581 156 136768381 3033 135143861 6845 135025277 279 134816849 924 134717269 6856 134541047 572 134141321 5486 132529673 2307 132428053 1845 132190853 69 131747027 8115 131343893 4722 131000629 7101 130969019 8091 130824313 6111 130791313 10265 130625039 10161 130144463 1541 129774767 4722 129519491 2265 129156877 1751 128999177 275 128685737 1427 128363407 2853 128244667 610 127162067 2379 126794849 7961 126357347 173 125951621 1991 125273839 294 124799063 2675 123791069 6569 123080939 4781 123023167 4419 122939039 7839 122375189 7821 121862093 67 121797059 4701 121689511 4601 121638109 7565 121438319 7791 120918439 5105 120775579 2348 120242699 8251 120150263 7942 119730427 5121 119673769 9117 119488751 6027 119389877 7725 118535579 785 118214329 5655 117972479 7679 117954029 4687 117403381 417 117077557 78 116341163 1092 116134709 721 116032043 4389 114810649 5086 114687613 1108 114028349 1295 113891777 7545 113480833 6561 112997761 3899 112988027 7515 112847837 2944 112342561 7757 112230257 3465 112216649 9047 112095703 1235 112031191 6672 111202297 5271 110858281 1595 110162333 291 110084641 4656 110063543 905 110036363 7557 109437287 8251 109115779 6759 108052349 7349 107172119 7319 106999667 9065 106853533 5171 106767559 4295 106470527 7295 106418513 615 106270231 1996 105620363 4556 104934737 294 104771467 6381 104768791 5645 104668231 107 103856351 1803 103482233 1598 101913557 6999 101689309 5303 101375783 4722 101253049 1121 100849337 189 100697369 779 100571089 9731 100164677 4722 99794183 165 99276179 3401 98560039 261 98311327 4941 98060789 2915 98006999 6999 97857719 1531 97503629 6981 97428193 2814 97277057 8847 96874343 5567 96796649 8057 96656257 3569 95658421 2841 95590673 1655 94940843 171 94825261 6201 94750429 7205 94447099 8421 94192963 1575 94031489 1899 93717947 1541 93578039 6839 93415849 8805 92926381 9489 92707679 2970 92563637 7586 91592887 1731 91456049 6761 91444303 5670 90727993 5499 90646379 6731 90409357 2424 90332507 4472 89749453 8829 89079323 1815 88331857 6738 88227949 6316 88018643 5489 87164149 233 86778451 1869 86599379 6579 86372207 41 86132413 2339 85863959 6551 85811549 6549 85739441 3161 85474121 2331 85217491 2331 85077221 5045 83987279 6479 83592671 6671 82804457 8271 82373881 597 81824027 6395 81004093 2331 80841349 709 80800471 372 80702159 6351 80296127 6335 80043727 15 79973281 6059 79091249 1662 78881779 6827 78632069 6269 78535763 1739 78328541 37 78318113 75 78298673 1731 78281327 6255 78255283 1784 78170111 4529 78031277 6245 77912929 765 77513297 2951 76787027 6195 76785041 6567 76394699 1457 76146277 1516 75888763 5567 75858667 5207 75845599 144 75391759 1899 75324439 2607 75256963 69 75255119 1060 74162639 3019 73958579 1528 73867301 8511 73402907 43 73370639 5855 71670377 5985 71526779 5979 71227879 2412 71095889 8291 70784171 1335 70599761 5415 70522457 1421 68643073 7841 68453989 1809 68414933 2772 68271611 1617 68249473 1226 68162971 179 68049383 2055 67913311 878 67872289 2791 67719671 731 67445311 2697 67410773 783 67085269 5705 67053989 5789 66742399 1731 66011287 6617 65809127 5735 65801353 756 65675941 6561 65465363 2498 64866293 3941 64851547 2956 64818599 2999 64803419 5691 64563271 2735 64393669 1905 64223923 3455 63863081 4224 63850649 5649 63399253 783 63238319 1929 62812721 3219 62278379 5579 62047541 6261 61921813 4115 61747817 189 61673551 1092 61625813 3003 61614661 945 61512271 2169 61379779 301 61348303 346 61315937 1211 60951967 629 60917959 4701 60549509 5501 60194353 676 60114449 118 59847269 5469 59463121 439 59236169 5441 58944229 3599 58671527 5415 58635307 4323 58491193 1133 58361861 879 58035847 4389 57971131 395 57696271 1335 57561397 2265 57542983 7281 57305021 3353 57204223 519 57181097 1115 56720539 7017 56369959 6419 56192761 827 55521833 3975 55192061 44 55101283 2619 54972221 3911 54711029 5229 54609977 2207 54384493 5739 54261827 5837 54224923 3965 53747909 2231 53649191 200 53380277 5165 53251993 67 53161991 453 53091359 5151 52688347 5829 52270199 5111 52158661 681 52157761 6869 52147577 5105 52052893 63 51990157 43 51496283 3635 51436499 569 50939467 174 50931313 541 50748091 2990 50459303 43 50349331 165 50205139 2814 49378559 728 49327277 4965 47794339 692 47784307 1365 47452687 371 47394679 671 47050183 3257 46818029 15 46792091 939 46572193 401 46315499 4811 45836117 1731 45821767 69 45779849 2015 45009397 242 44808791 189 44762677 5250 44747047 41 44706773 2182 44561519 4719 44409923 3123 44222309 4701 44144069 1049 43945247 3733 43825841 4025 43786579 2613 43659839 4671 43469267 2263 43424039 1869 43416179 445 43219651 129 43137209 5921 43100969 4641 43043437 4901 42896779 4749 42693419 4619 42526591 3299 42361409 4601 42118579 4722 42117073 5477 41721271 3537 41578091 924 41378167 881 41275957 2547 41205163 5385 41190703 1257 40901489 4521 40886947 105 40880027 5781 40635109 267 40472743 569 40397983 2045 40229957 5681 40129619 2989 39995609 639 39916799 11 39823349 4461 39590021 5567 39439271 1235 39312047 1133 39199309 2878 38750659 1733 38589347 1586 38548589 4389 38440607 69 37971403 3299 37953677 4449 37763387 615 37539119 2211 37515113 28 37416109 1529 37395433 619 37147471 486 36874879 2271 36699599 3257 36687223 336 36165163 419 35834941 1092 35707949 231 35665757 2375 35553527 4215 35452409 4209 35354867 2692 34964653 572 34833763 1363 34781633 4077 34613129 2691 34248917 881 34231991 885 34150979 4131 34064011 2150 33788309 4109 33727987 2061 33400109 1731 33368141 924 33154489 1751 32592389 2263 32125901 3455 31992239 1557 31857479 2050 31680497 4155 31317919 2801 31234387 3012 31233343 2879 31152679 1595 30948427 2618 30933509 249 30713497 173 30548603 629 30441977 2990 30331583 5009 30228901 2399 29754523 1992 29648849 3849 29587277 3845 29407643 641 29238743 1092 29230699 879 29188619 3819 28923451 1403 28914209 3801 28904509 96 28789157 545 28762319 3791 28689629 689 28684697 519 28684339 221 28338181 536 28259963 551 28247701 1541 28123829 1705 27989383 2098 27883949 309 27774211 190 27769877 3725 27729313 1280 27617159 3945 27598603 5031 27562541 4799 27469957 3459 27450677 827 26736851 1092 26422007 3465 26162209 2620 26071181 702 26034677 3531 26010077 3605 25864919 881 25748213 1705 25674403 15 25526363 765 25180511 881 24905743 2334 24799679 721 24764953 109 24643709 3509 24626179 3915 24624049 242 24314761 4929 24225869 765 24215263 2263 23918399 1365 23891327 3455 23577269 3687 23444563 2651 23400781 1739 23364563 1863 23223413 892 22987589 3389 22902743 4347 22898411 56 22802737 4097 22407503 1705 22334827 999 22181129 3329 22103581 1049 21544603 150 21471013 4347 21362351 64 21196421 4505 20936221 2711 20902523 2990 20837447 3737 20738573 2963 20734139 105 20659031 3987 20467339 1927 20377801 967 20341369 1541 20241379 569 20175011 4347 20044711 639 19816477 819 19672127 3135 19593323 422 19411477 2081 19217257 52 19136107 2409 19130681 1169 19000529 3081 18966289 2399 18927709 615 18803777 3065 18559589 147 17909263 447 17844139 2375 17826203 1115 17738713 349 17644769 2969 17639903 210 17549849 2961 17347657 2661 17326753 915 17190493 580 16933933 849 16877911 1916 16816147 3489 16674479 2457 16646387 747 16459321 3879 16421143 185 16295131 3185 16156769 2841 16048829 250 15926903 569 15728099 697 15645919 1769 15638027 2795 15620629 1380 15598181 111 15596881 1547 15591131 96 15559741 249 15535241 1092 15304277 2765 15017939 2739 14738203 641 14608163 209 14471537 2835 14449789 2399 14175149 2661 14171593 1185 14169161 899 13991609 3525 13700917 401 13689527 2615 13666901 111 13607821 1859 13588063 521 13521181 2729 13418789 2589 13380359 939 13373117 18 13329193 837 13318303 1151 13299739 2239 13021837 629 13007549 2549 12804329 2529 12760541 2586 12758477 789 12703319 2519 12675643 1092 12636581 2027 12632611 1043 12522509 2501 12346909 939 12305011 721 12288217 1259 12263627 2475 12224039 2471 12206347 1787 12203797 3299 12164777 2465 11971237 1751 11956039 1995 11939281 575 11939129 2195 11881979 871 11870627 2435 11714471 63 11710351 2291 11678047 57 11584127 2546 11563967 2265 11543071 1043 11445719 2391 11395369 2351 11331179 2379 11328007 43 11293127 2375 11003449 249 10994453 43 10969187 1541 10953539 2339 10585037 21 10464031 825 10372717 2111 10210241 52 10172663 1739 10093327 168 9977029 301 9903521 1397 9832187 809 9707249 2445 9589339 1031 9577609 1169 9492467 1125 9477049 971 9144503 1783 9111941 1287 9075929 2129 9075751 1595 9018539 2555 8981443 2341 8974379 2295 8906309 2109 8718989 2675 8678717 2661 8654879 2079 8562443 878 8546399 267 8517739 1997 8427889 1446 8426401 445 8401229 905 8401091 173 8225449 2162 8211377 2025 8082209 2009 7919537 234 7787203 43 7779539 1971 7666441 2279 7651307 1665 7646591 1133 7588943 1667 7499929 857 7469719 863 7349653 361 7290197 2027 7154363 765 7135993 2027 6995669 1869 6957871 291 6921059 1859 6809399 1859 6789869 765 6781183 46 6768379 1323 6700861 939 6645277 2205 6615403 1829 6589859 1799 6526433 629 6388111 301 6384421 1655 6381377 1785 6308119 1233 6301991 1611 6295649 305 6183311 939 6178547 1191 6112097 567 6098777 1745 6041741 1521 6001379 1731 5822051 445 5792669 941 5701057 570 5630231 1565 5603797 1619 5552777 1665 5534801 249 5415089 276 5354627 1635 5289377 1625 5226761 557 5186693 844 5179087 2241 5041021 924 5038843 534 4950973 1707 4925203 809 4923617 111 4921069 419 4900039 64 4790803 1199 4783091 51 4730113 1705 4583291 276 4561709 1509 4540271 1308 4507271 1899 4417877 1485 4356917 723 4308427 1108 4283551 1871 4270339 615 4218059 1451 4207573 905 4118011 361 4116403 1705 4082083 39 4074397 242 4068377 1425 4045589 1421 4002211 1115 3979909 1043 3957469 69 3904301 1092 3829099 1665 3787891 581 3768691 1705 3733277 1365 3689047 1691 3682453 611 3655871 807 3648949 221 3628799 10 3609187 42 3588439 57 3570059 539 3502861 441 3470381 498 3351437 84 3309289 1445 3184067 401 3070523 11 3054127 276 3027029 1229 3020627 1577 3004069 131 2982493 1719 2962189 1037 2908537 65 2901149 193 2892187 55 2881199 1199 2872087 165 2845121 633 2812721 1487 2739343 1019 2738969 1169 2695529 44 2669041 599 2666203 281 2634323 505 2597069 84 2518889 1121 2494927 111 2426159 281 2415739 105 2398397 1199 2379409 1371 2377289 1089 2361661 575 2348047 11 2329781 67 2275381 737 2261261 749 2224543 765 2206049 1049 2194303 417 2179313 329 2140373 615 2123809 459 1961189 989 1952141 597 1883179 135 1877549 123 1861843 69 1845743 611 1837603 719 1818671 96 1780153 869 1768139 939 1757381 441 1742651 881 1735513 11 1704317 397 1683109 575 1682743 361 1642577 905 1621513 1179 1584839 767 1562831 375 1549679 879 1530041 567 1453351 95 1449059 165 1445471 96 1422919 125 1406813 827 1406299 276 1394339 813 1369237 67 1359227 291 1338511 437 1316057 881 1313009 809 1295627 1011 1293337 567 1281233 881 1278847 767 1269673 345 1244413 43 1206901 431 1192739 771 1163779 663 1131931 663 1101869 741 1094617 329 1089307 881 1065371 459 1060483 881 998771 342 980699 699 952013 135 942841 609 937103 276 935897 197 903113 57 891757 368 889159 82 865861 15 850859 651 829271 401 828827 321 828521 569 824969 641 819839 639 809849 64 800881 881 796457 323 794429 629 793157 276 779497 54 759527 615 756731 43 749699 611 748081 663 732857 767 732661 717 721453 465 719963 125 719309 591 687377 585 685309 399 683779 237 657997 617 645377 69 644681 335 605791 52 598337 67 598321 725 595759 755 568819 29 563833 84 541319 519 535981 43 533161 561 531721 429 528007 189 520199 43 518663 75 518569 142 505387 46 488857 431 484651 239 477709 272 472877 485 462877 431 460219 21 453457 465 448909 39 431741 191 423659 459 416327 455 398179 54 391169 441 390919 221 383233 407 382121 105 376591 179 370229 429 362879 9 361117 107 356393 525 346981 465 344051 267 329921 129 329653 69 326041 112 323287 189 315587 272 315071 507 266789 429 243407 272 234601 189 218129 329 205501 67 193777 105 192139 269 191959 122 189869 179 184507 54 180619 11 176879 71 168611 96 162923 189 153253 231 147053 153 138037 111 135143 25 133501 11 130313 75 129709 149 128417 279 125249 249 120389 129 118933 21 118229 189 107879 231 102089 11 99443 236 90949 96 90751 75 89801 67 88013 281 85651 43 83129 43 81803 177 77123 231 76189 44 74351 98 72389 189 69947 111 64979 179 64789 48 60023 90 58879 43 55739 69 55277 165 52777 67 50933 15 48827 155 47029 129 40319 8 37127 135 33431 99 32989 9 31877 125 28471 69 27931 15 25199 111 23999 101 23267 37 22577 105 18349 29 16517 81 16337 15 11449 105 10379 53 9869 69 9641 29 5083 11 3569 41 2627 35 2047 21 1829 29 1643 15 1387 17 961 15 901 15 527 15 391 11 299 11 221 11 121 9 119 5 61 59 60 1 59 57 58 1 57 1 56 1 55 1 54 1 53 51 52 1 51 1 50 1 49 1 48 1 47 45 46 1 45 1 44 1 43 41 42 1 41 39 40 1 39 1 38 1 37 35 36 1 35 1 34 1 33 1 32 1 31 29 30 1 29 27 28 1 27 1 26 1 25 1 24 1 23 21 22 1 21 1 20 1 19 17 18 1 17 15 16 1 15 1 14 1 13 11 12 1 11 9 10 1 9 1 8 1 7 5 6 1 5 3 4 1 3 1 2 1 1 0 )"; void init(int key, int value) { stringstream convert; convert << TABLE; while (convert >> key >> value) table[key] = value; } int power(int a, int b, int p) { if (b == 1) return a; int x = power(a, b >> 1, p); x = 1ll * x * x % p; if (b & 1) x = 1ll * x * a % p; return x; } bool check(int n, int h, int a) { if (n % a == 0) return false; int now = power(a, h, n); if (now == 1) return true; while (h != n - 1) { if (now == n - 1) return true; now = 1ll * now * now % n; h <<= 1; } return false; } bool prime(int n) { int h = n - 1; while ((h & 1) == 0) h >>= 1; if (!check(n, h, 2)) return false; if (!check(n, h, 7)) return false; if (!check(n, h, 61)) return false; return true; } int solve(int n) { if (table.count(n)) return table[n]; if (prime(n)) return n - 2; return 1; } int main() { freopen("factorial.in", "r", stdin); freopen("factorial.out", "w", stdout); init(0, 0); int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); printf("%d\n", solve(n)); } return 0; }
035966_L3
管理员
LV 6
MOD
@ 2025-4-28 19:17:28