关于 N-factor 的若干思考

· · 算法·理论

前段时间看到一个有趣的题：

输出任意 1000 个 [1,10^9] 内的整数。

得分为这些整数的因数的并集大小。

突然想到以前出的一道题时间复杂度就和因数的并集大小有关，遂做了做。

part1 简单思考

显然是 NP 问题，那么使用模拟退火还是爬山？

数集大小太大了！有 10^9 个数，模拟退火会因为有概率接受错解，所以会越来越劣！模拟退火直接 spfa 了。

但是爬山呢？虽然前期很快，可是后面就也 spfa 了。

怎么办？我们可以定一个阈值，一旦超过这么多次没出新解，就随机换几个。

分解因数可以用 Pollard Rho。

这样跑一天大概就有 2 \times 10^5 了。

part2 优化！

数集大小太大了！这是最大的阻碍，找 1000 个数如大海捞针！

如何减小？首先一个数乘 2 后答案一定不会更劣，于是直接砍半！变成从 [5 \times 10^8,10^9] 中选。

如果它们是反素数的倍数话是很优的，多试几下，再观察构造出的解，60 的倍数应该是很优的。

如果一个数由超大素数构成，没几个因数，这能选？直接 pass！

这启发我们只用前几个素数构成的数中选。再次观察构造出的解，不断缩小范围，大概前 520 个素数就够了。

没几个因数，这能选？直接 pass！

再次观察构造出的解，不断缩小范围，注意到当答案 \ge 2.5 \times 10^5 时，因数个数全部不小于 360，于是只选因数个数 \ge 360 的。

数集大小变小了，模拟退火又行了！根据测试，模拟退火吊打爬山，据 rk1 所说，祂是以 0.001 \% 的概率接受的，快去试试吧！

我们优化了这多，候选的数只有 2.2 \times 10^5 了，质因数也只有前 520 个素数了，用 Pollard Rho？不如预处理！

开多线程，压榨 CPU，然后让 AI 激进优化。

挂在后台多跑几天。

相信您看了这些，一定自己的想法了，又什么新的思考可以再评论区说说，也可以付诸实践去这里交一下，相信凭借您的实力一定吊打我。

附赠一个 2 \times 10^5 的解：

:::info[score：200003]

831058800 972546540 743759280 972389880 770322168 983525760 486333120 951680520 568632960 455162400 947829960 857969280 845797680 672647976 621500880 962794080 888579720 981522360 956531520 595983960 792625680 874326600 961517700 731273400 923410488 564725700 581123520 759121440 960600060 398820240 953480640 675972360 909585000 948841740 539233200 985766760 496520640 702361800 836936100 772448040 841140300 802813440 614493180 890366400 832854960 782334000 747191340 736123080 816444720 937167840 913969980 503435520 875891520 885452400 397219680 565699680 637617960 782779140 917495040 448371000 988033200 983813040 673965600 769925520 905392800 962270400 662800320 530749800 764492400 885631320 730819800 611808120 905279760 494053560 564425400 311295600 580373640 953631360 733299840 813711360 965690880 847476000 918729504 973717920 948205440 992071080 867474300 914564640 976925040 973153440 814959600 871006500 884474640 907920000 663371280 570702240 904897440 959878080 965314350 874593720 952638720 993373920 533016120 804069420 897951600 480513600 708314880 828938880 588893760 772490880 654249960 858715200 850475340 910942200 788597280 940359420 996080400 971397000 900359460 502005504 916642440 978370800 958305600 652113000 640921680 997978800 702372000 828748800 946639980 949221000 933177600 550596816 833692860 815356080 818978160 977180400 305379360 998067840 955134180 856132200 937025040 766558800 967527120 845177760 582036840 871075920 591300360 619254720 926319240 720355680 926164800 457777320 778483200 773110800 833817600 937379520 764394120 883505700 733289760 955500000 610705200 788795280 990007200 947353680 827205120 941475744 935267400 934612800 858743424 936230400 983671920 832487040 708489600 828439920 876292560 702324000 720248760 977920020 869709120 965827800 576338400 965042400 942303600 973217700 627190200 756149940 985284300 987261660 525883680 600339960 950531400 668222100 772129800 975522240 933269400 556340400 983040240 832720980 875852640 482244840 782178600 817601400 768474000 753248160 825986700 499181760 945764820 790652016 936139680 920293920 762841800 442194480 922894560 692349480 992217240 951830880 644360640 634601520 837254880 910395360 716695200 962400600 861925680 929049660 970780800 838091520 882926352 399207600 651067200 604323720 780412080 887250672 595183680 914868240 872660880 979999020 948087000 800754240 827318520 853512660 916067460 929548620 955563840 827525160 979937280 992730816 979542720 996629760 740607840 953453592 323122800 941066280 950980800 875879100 998252640 816601500 811928520 745972920 638101800 861471000 703377720 974036700 591399900 940834440 839624016 735568470 681192720 862416000 795789540 755879040 956462760 986682312 832616820 809091360 626786160 688973040 874798920 845413800 807436080 943125120 640817100 832469400 723345840 815057100 943105800 427695840 783367200 978257280 913830840 871182000 704088000 847721160 731771040 998243400 613925760 898449552 697334400 744840720 976374000 698063520 552360600 690459000 608202540 776982960 989068080 705185520 812649600 942365760 924610680 984569040 771381000 528292800 886699440 938534688 747618300 977248800 958885200 938211120 821979900 960359400 937083840 751816800 559685280 880461120 626139360 608353200 972429120 787970400 709964640 883935360 862443120 826868952 849515940 904434300 861276780 840886200 968130240 962967600 930398040 842237760 916695360 568123920 923796720 981608628 768916800 609479640 827164800 841386000 414506400 991186560 934025400 944887680 881865600 517532400 766517760 991017720 730352700 933801840 874083600 855782928 910629720 714178080 785104320 843102720 851529000 868748400 920536320 689618160 907736760 961598880 847446600 617329440 600032160 903417900 970224360 917454720 677771640 716072400 879710832 910288800 616132440 434740320 782215560 688023840 844268040 886013100 846073800 655934400 749094360 716035320 537356400 985234320 881136000 935996880 975478560 737932260 958820940 659084160 798585480 928488960 938521584 874905408 667403880 816622560 782167680 634593960 543125520 509710320 882784980 998393760 628808400 776872800 973143600 863854320 809287200 666847440 777854700 814685760 916461000 854284200 715199520 794761968 732473280 837837000 852739272 955794840 764014680 757334340 751121280 659758176 727317360 908157600 839442240 957159720 911324400 875192640 704932200 999461232 913258080 838419120 652122240 933387840 882789600 887978520 686551320 804619200 947124360 862942080 701457120 804609960 826156800 518608800 976480680 391018320 640864224 681698160 792454320 928846800 853299720 968054976 969876600 877562784 925302420 941194800 801942120 478961280 948263400 932383200 721670040 928735500 621673920 787891104 713651400 723643200 740345760 944667360 946974600 909049680 825869520 642987072 513738720 414489240 881953800 809461800 856007460 941068800 666167040 754488000 744637740 792552600 696672900 567206640 856089000 630260400 669271680 975580200 954518040 627757200 610992480 920818080 887551560 878439870 713993280 715391040 596292480 964905480 682803000 915390000 843002160 848592360 392530320 982035600 922983600 913472280 651772800 497158200 514476144 960146880 947802240 948249120 950590368 794621520 590171400 996781968 867877920 991596060 985733280 930908160 821842560 880129800 969237360 922599720 915734160 523286400 920211600 736076880 806721300 792348480 835851240 936018720 930468000 858873600 642854520 958645800 875429100 841013460 725749200 593651520 846967968 712444320 870345000 919273320 936381600 985137840 821325960 914538240 984735360 645971760 861402240 879145344 965956320 837003024 878040540 982759800 878358600 997258080 793971360 808405920 869678880 833536080 789253920 943937280 632268000 801450720 783992160 685210680 639084600 891880416 561768480 774635400 977124960 879590880 737953920 792923040 914798016 858433680 852387480 723359520 883209600 737499000 696346560 878100048 889728840 764347584 876964608 935838540 735731100 719355000 731638440 943936560 510310080 621619200 767138400 796874400 689876460 689944320 917935200 654857280 826469280 529576320 965661840 849701160 849582720 595590480 769824720 951615000 756996240 734000400 966423276 781435200 867506640 869791230 939299760 999061140 589139460 803453280 901181400 626169600 779523360 797882400 964261200 820048320 798847920 981558240 777262500 622162800 992565000 767400480 798860700 565224660 935131680 901655820 785484000 884822400 859046760 946665720 535051440 976029600 820479660 916959120 615303360 902341440 929756520 776481552 962978940 959527800 852936480 728065800 982839000 964852680 934983000 765182880 915037200 991428984 861080220 903451500 797957160 967233960 543090240 818532540 883136520 880664400 722988000 746638200 999153792 978270480 860933700 676146240 676599840 569923200 753781392 982144800 854413560 994672800 603061200 990046680 750012120 975445380 730548000 835670160 878717070 770299920 672953400 817598880 659699040 911214000 956493720 995966400 651039480 884842200 541653840 828204300 384420960 853578000 943795800 809128320 900761400 792866880 870749880 818652240 953528940 933847200 906703560 685571040 663542880 970094664 643428240 739103040 928006200 782967360 996964200 965667360 895098960 764264160 884905560 857961720 579262320 952894800 881416800 851202000 373138920 979680240 831742560 706633200 891867600 643519800 455402640 927232020 913792320 941311800 527875920 931733880 752446800 842315760 945030240 915794880 275093280 893057760 964526640 634397400 909640800 761315940 977644800 867252960 884933280 724274460 838681200 981708000 495028800 894316500 875085120 925058400 861478800 875430360 319057200 749002800 662020800 970114860 972906480 982880640 762177780 935399640 885213420 995163000 958223700 634898880 840687120 942014880 584064000 723159360 797213340 521274600 970329360 826076160 919278360 981730620 857115840 905030496 923177520 827857800 888994260 883436400 738796800 976780800 564429600 731633760 836608080 985175100 943324200 857929800 793485000 903095460 886347000 680996160 933377760 224471520 761687640 964599720 884817360 993632640 816435840 605500560 932344560 797443920 837522000 962308200 765186240 907751040 962685360 963122160 463228920 685825140 545798400 923466720 498047760 920724480 991118700 967453200 770711760 997783380 972182400 937394640 990482220 796924800 961333560 678328560 717886260 701850240 850651200 924073920 783380640 947550240 582721920 892128600 479458980 936603360 957869640 898037760 954147600 919158240 984293640 938361600 751647600 657777120 658274400 917426400 529347000 890274000 887140800 860358240 773770368 849466800 526949280 870022440 901402560 850024800 697258800 872574300 802308780 578609280 776134800 445478880 985612320 889986240 734378400 983346000 983116800 979832700 709373280 983372544 892699920 992082000 845984160 833484960 571614120 883297080 567289800 973462644 920959200 618585660 908530560 941096520 813396600 824658240 814408560 968526720 843297840 824481504 927103320 999611280 957630960 972039600 777519600 846345780 702013620 959898240 830919600 648133200 691429200 882532560 619278660 940988880 930061440 857850840 986693400 535318560 785888640 921619776 991738440 425890080 486735480 820871520 843312600 874523520 949754520 893138400 794928960 564006960 863428020 673089480 607572000 964517400 700122150 755844480 550020240 645543360 831156480 944485920 901311840 970617600 910072800 885530880 983355660 718952400 904667400 817522860 990240480 972682200 843542280 794596320 991637640 822013920 950607840 804667500 823616640 665584920 981810180 828772560 428631840 786338280 995437380 788184600 835567920 906527160 768731040 480193560 864289860 989504040 716113440 921402720 745491600 848832600 938571480 536079600 787615920 726153120 897008112 902494320 781522560 731006640 786693600 953272800 684383700 935020800 825973200 998623080 942013800 958459320 677615400 860082300 408816720 873611640 761634720 700223040 931467600 735926940 979355520 608577480 604905840 838123440

:::

PS：感觉 spj 有问题啊，有时候莫名其妙把答案吃了 1。

鸣谢：

@Believe_in_dreams

@aaron0919

@yanqijin

@Glaciaxion

集中谷民们的智慧，找到最优解吧！