「题解」「SCOI2009」游戏

题目链接:GMOJ 1038/Luogu P4161/SCOI 2009

题解

解法 A (正解)

思路

找规律,发现操作循环。

代码

#include<cstdio>
typedef long long ll;
const int MAXN=1000+5;
bool vis[MAXN];
int n;
int cnt,prime[MAXN];
ll f[MAXN];
inline void Prime(int);
int main(void){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    register int i,j,k;
    register ll ans=0;
    scanf("%d",&n);
    Prime(n);
    f[0]=1;
    for(i=1;i<=cnt;++i)
        for(j=n;j>=prime[i];--j)
            for(k=prime[i];k<=j;k*=prime[i])
                f[j]+=f[j-k];
    for(i=1;i<=n;++i)
        ans+=f[i];
    printf("%lld\n",ans+1);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
inline void Prime(int n){
    register int i,j;
    for(i=2;i<=n;++i){
        if(!vis[i]){
            prime[++cnt]=i;
            for(j=(i<<1);j<=n;j+=i)
                vis[j]=true;
        }
    }
    return;
}

解法 B (需要前置技能)

思路

本解法十分显然,但需要前置技能(解法 A),代码长度较长,但时间复杂度降到了 $\Theta(1)$ 的级别。

代码

代码无需多说,也没什么细节需要注意的。

#include<cstdio>
typedef long long ll;
const ll ans[]={0,1,2,3,4,6,6,9,11,14,16,20,23,27,31,35,43,47,55,61,70,78,88,98,111,123,136,152,168,187,204,225,248,271,296,325,356,387,418,455,495,537,581,629,678,732,787,851,918,986,1056,1133,1217,1307,1399,1498,1600,1708,1823,1950,2083,2218,2356,2506,2671,2842,3025,3211,3409,3610,3830,4067,4316,4568,4829,5105,5406,5722,6051,6393,6746,7112,7506,7928,8372,8821,9282,9770,10293,10845,11423,12013,12621,13255,13930,14653,15410,16176,16960,17785,18663,19591,20553,21545,22560,23616,24734,25933,27174,28439,29728,31076,32509,34026,35595,37204,38850,40557,42366,44282,46270,48301,50360,52517,54796,57199,59689,62243,64838,67535,70375,73378,76499,79669,82896,86259,89808,93544,97408,101346,105371,109528,113898,118515,123298,128161,133123,138260,143662,149346,155217,161203,167304,173602,180223,187188,194394,201727,209179,216887,225004,233478,242246,251189,260296,269680,279534,289857,300546,311405,322443,333839,345784,358285,371203,384343,397730,411531,425953,441059,456667,472506,488623,505255,522633,540796,559541,578622,598040,618004,638849,660655,683132,706001,729237,753154,778157,804249,831083,858442,886231,914803,944588,975676,1007714,1040309,1073406,1107489,1142976,1179941,1218033,1256772,1296102,1336565,1378646,1422511,1467723,1513662,1560288,1608264,1658153,1710050,1763441,1817764,1872970,1929640,1988528,2049843,2112903,2177002,2242117,2308930,2378345,2450550,2524753,2600227,2676925,2755570,2837222,2922075,3009300,3097939,3187910,3280268,3376122,3475560,3577799,3681810,3787349,3895580,4007781,4124158,4243812,4365410,4488795,4615345,4746534,4882547,5022247,5164208,5308385,5456077,5608963,5767544,5930385,6095779,6263781,6435911,6613993,6798505,6987901,7180330,7375721,7575773,7782710,7997065,8217094,8440659,8667488,8899739,9140016,9388512,9643384,9902531,10165513,10434616,10712858,11000633,11295797,11595731,11900036,12211421,12533095,12865645,13206691,13553187,13904850,14264665,14636001,15019870,15413510,15813151,16218675,16633663,17061853,17504131,17957511,18418083,18885444,19363284,19856106,20365018,20886445,21416170,21953633,22502996,23069688,23654627,24253578,24862140,25479632,26110444,26760714,27431758,28118910,28816859,29524995,30248724,30994342,31763154,32550426,33350018,34161082,34989834,35843243,36722969,37623961,38538864,39466642,40414595,41390540,42395999,43425108,44470326,45530615,46613390,47727748,48875865,50050571,51243342,52453405,53688691,54959424,56268254,57607048,58966572,60345981,61753831,63201526,64692137,66216763,67764588,69334382,70936798,72584395,74279577,76013285,77773910,79559305,81381225,83253875,85179845,87149249,89149075,91176899,93245998,95372229,97558561,99793501,102062615,104363895,106711118,109121778,111600554,114134202,116705815,119314243,121974988,124706573,127514054,130383070,133295058,136248424,139260259,142351499,145527797,148773538,152068169,155408850,158815052,162310911,165901151,169568417,173291577,177066812,180915029,184863771,188918534,193059430,197262777,201524816,205868795,210324461,214898330,219569114,224310043,229117452,234017083,239040338,244195775,249460339,254802436,260218466,265738585,271396945,277202139,283129321,289144535,295242993,301456932,307824977,314356624,321023550,327789549,334649288,341637377,348797935,356141163,363634328,371238934,378949177,386801433,394844883,403092443,411507682,420046804,428704287,437521813,446551722,455807005,465249543,474830686,484543355,494434944,504562393,514939726,525527157,536269941,547158658,558246803,569597371,581224252,593083626,605117138,617314792,629733181,642443002,655461536,668737718,682206885,695860533,709759227,723979796,738543076,753392290,768456802,783728737,799272915,815172700,831452246,848050243,864887178,881953128,899322732,917087901,935271624,953809031,972615020,991675037,1011070969,1030905654,1051202104,1071889555,1092876582,1114146494,1135789191,1157918165,1180558496,1203631340,1227037003,1250758849,1274892125,1299559906,1324795149,1350510875,1376593435,1403028629,1429922644,1457405859,1485514730,1514155683,1543203181,1572641892,1602588815,1633186342,1664474165,1696351486,1728682008,1761445285,1794769597,1828814019,1863617807,1899069884,1935027797,1971466974,2008523557,2046376390,2085069567,2124477324,2164444125ll,2204944946ll,2246127897ll,2288186708ll,2331170910ll,2374944919ll,2419337740ll,2464324227ll,2510066877ll,2556771251ll,2604494051ll,2653092123ll,2702371962ll,2752305410ll,2803076889ll,2854908075ll,2907857789ll,2961774353ll,3016448100ll,3071844250ll,3128162791ll,3185648506ll,3244364764ll,3304143118ll,3364759211ll,3426176909ll,3488609875ll,3552329115ll,3617404129ll,3683644973ll,3750812077ll,3818868910ll,3888039623ll,3958620113ll,4030694695ll,4104054622ll,4178434675ll,4253798862ll,4330394472ll,4408538904ll,4488321060ll,4569519033ll,4651842318ll,4735247672ll,4820010876ll,4906476594ll,4994736912ll,5084558311ll,5175624602ll,5267881025ll,5361632211ll,5457255131ll,5554842531ll,5654142432ll,5754818741ll,5856810174ll,5960441397ll,6066126885ll,6173974428ll,6283701754ll,6394940039ll,6507631461ll,6622124245ll,6738864791ll,6857978989ll,6979157639ll,7101997795ll,7226445406ll,7352875310ll,7481764169ll,7613253926ll,7747013059ll,7882597151ll,8019945383ll,8159473589ll,8301699931ll,8446769883ll,8594331579ll,8743910527ll,8895427207ll,9049331616ll,9206196601ll,9366172128ll,9528873964ll,9693797200ll,9860852104ll,10030525166ll,10203444811ll,10379770883ll,10559080583ll,10740831340ll,10924931305ll,11111897941ll,11302407501ll,11496649064ll,11694166218ll,11894357291ll,12097132737ll,12303060819ll,12512858130ll,12726732383ll,12944198756ll,13164595478ll,13387825436ll,13614512988ll,13845431958ll,14080805456ll,14320115376ll,14562646835ll,14808285424ll,15057708438ll,15311761934ll,15570675608ll,15833884237ll,16100636108ll,16370803829ll,16645102455ll,16924464220ll,17209145957ll,17498519429ll,17791774046ll,18088779028ll,18390299936ll,18697344550ll,19010199275ll,19328185010ll,19650420611ll,19976773039ll,20308074230ll,20645397422ll,20989055317ll,21338329924ll,21692252275ll,22050672926ll,22414516095ll,22784933595ll,23162249395ll,23545709392ll,23934271129ll,24327753869ll,24727156223ll,25133732686ll,25547828658ll,25968624018ll,26395003862ll,26826776509ll,27265010674ll,27711074049ll,28165345366ll,28626916844ll,29094594714ll,29568189289ll,30048827936ll,30537983178ll,31036093648ll,31542172860ll,32054919139ll,32574145537ll,33101072871ll,33637272712ll,34183218205ll,34737861066ll,35299789674ll,35868789249ll,36446196097ll,37033709594ll,37631824690ll,38239430818ll,38855010405ll,39478304136ll,40110766887ll,40754246129ll,41409245858ll,42074572214ll,42748621670ll,43431106384ll,44123576445ll,44828039580ll,45545054957ll,46273316616ll,47011088823ll,47758082837ll,48515954457ll,49286853483ll,50071414346ll,50868227777ll,51675405572ll,52492664809ll,53321790300ll,54165067429ll,55023197297ll,55894677570ll,56777447396ll,57671203191ll,58577896159ll,59499981893ll,60438193000ll,61390936476ll,62356017675ll,63333073337ll,64324194785ll,65332058203ll,66357434382ll,67398598180ll,68453223508ll,69520908559ll,70603888232ll,71705076914ll,72825301246ll,73962674804ll,75114713008ll,76281000319ll,77463912237ll,78666575137ll,79889917242ll,81131914957ll,82389864969ll,83663349085ll,84954946378ll,86267969252ll,87603420299ll,88959165726ll,90332267436ll,91722264269ll,93131965301ll,94564921811ll,96022203051ll,97501548558ll,98999798351ll,100516425306ll,102054461912ll,103617749612ll,105207405771ll,106820987034ll,108455156577ll,110109349227ll,111786772339ll,113491593995ll,115225043914ll,116984444361ll,118766223652ll,120569807381ll,122398600243ll,124257075520ll,126146598389ll,128064289941ll,130006300065ll,131972040551ll,133965174080ll,135990465810ll,138049392322ll,140138902214ll,142254820391ll,144396494515ll,146567931024ll,148774232292ll,151016929662ll,153292814315ll,155597432252ll,157930020989ll,160294887144ll,162697537961ll,165139589171ll,167617597202ll,170126825416ll,172666450793ll,175241066390ll,177856618213ll,180514863855ll,183212054568ll,185943122312ll,188707238814ll,191509268101ll,194355568996ll,197248118105ll,200182877692ll,203154366440ll,206161765751ll,209210305125ll,212306734650ll,215453184594ll,218645374888ll,221877405056ll,225148372390ll,228463928649ll,231831317974ll,235252791803ll,238723820584ll,242238106889ll,245794599859ll,249399381601ll,253060280355ll,256779627993ll,260552564683ll,264372446164ll,268238120513ll,272156052482ll,276134692273ll,280176565688ll,284276410040ll,288427113649ll,292627499395ll,296884449016ll,301206972463ll,305597861214ll,310051495326ll,314560205170ll,319122798205ll,323746659718ll,328441342645ll,333209887681ll,338046344401ll,342942408883ll,347896803977ll,352917538518ll,358014816334ll,363191837821ll,368442307795ll,373757394476ll,379135648951ll,384585624470ll,390118316230ll,395737102460ll,401435216507ll,407203321410ll,413039853891ll,418953890989ll,424957296394ll,431053708853ll,437235795593ll,443493626599ll,449825581962ll,456241275517ll,462753393721ll,469365943387ll,476071080066ll,482858110773ll,489725383995ll,496683248414ll,503745148015ll,510915363490ll,518185630677ll,525544451047ll,532990017359ll,540533511079ll,548189274537ll,555961836768ll,563842494708ll,571818966004ll,579889205275ll,588065207835ll,596362372780ll,604785459785ll,613325149310ll,621968457024ll,630713200422ll,639572085807ll,648561674937ll,657687142087ll,666938387037ll,676301564345ll,685774468635ll,695370557493ll,705107486530ll,714990931444ll,725010091661ll,735150138513ll,745408824452ll,755800520881ll,766343974694ll,777045306277ll,787893092424ll,798871398499ll,809977766202ll,821227723044ll,832641286737ll,844224855443ll,855966393492ll,867848981159ll,879869816425ll,892045506340ll,904397535591ll,916932622159ll,929637921709ll,942495539191ll,955502460050ll,968676334546ll,982040200877ll,995601286295ll,1009345773349ll,1023254606037ll,1037324694610ll,1051574721415ll,1066029208513ll,1080696124591ll,1095560713935ll,1110602493920ll,1125818361297ll,1141228319560ll,1156858331646ll,1172716951103ll,1188788582220ll,1205051283087ll,1221501719211ll,1238161366709ll,1255057902769ll,1272200375557ll,1289572315975ll,1307150420390ll,1324930934998ll,1342936786986ll,1361197671394ll,1379723068032ll,1398495392607ll,1417490092525ll,1436703101383ll,1456158699765ll,1475888764993ll,1495903486004ll,1516183934622ll,1536703993094ll,1557459476699ll,1578476148379ll,1599787909637ll,1621405824525ll,1643309773051ll,1665471817396ll,1687887677315ll,1710584875844ll,1733599281643ll,1756942796500ll,1780594225510ll,1804523575124ll,1828726241588ll,1853231840544ll,1878078521962ll,1903278837236ll,1928810454136ll,1954641531896ll,1980766953640ll,2007218276106ll,2034036325376ll,2061234357322ll,2088788516103ll,2116665185001ll,2144858936892ll,2173403175320ll,2202341606107ll,2231688453890ll,2261418067666ll,2291494818317ll,2321913119721ll,2352708241781ll,2383926705567ll,2415584018270ll,2447652863191ll,2480095151903ll,2512905159630ll,2546120572871ll,2579790652383ll,2613931921957ll,2648515601309ll,2683501004908ll,2718881926599ll,2754698808770ll,2791004040226ll,2827815023108ll,2865101499418ll,2902820283286ll,2940964457767ll,2979577185567ll,3018714402027ll};
int n;
int main(void){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&n);
    printf("%lld\n",ans[n]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}