Submission #898299

#	Time	Username	Problem	Language	Result	Execution time	Memory
898299		PersistentLife	Present (RMI21_present)	C++14	100 / 100	2989 ms	596 KiB

Main

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int buc[45],gc[45][45];
const int B=40;
ll tab[2005]={0,33751126,75992750,116437822,170615006,230739902,290855294,354085630,432245118,531108606,568870830,612293374,651920694,705855166,765146974,826166750,889429438,965887838,1063269086,1145670542,1233666414,1357252302,1505105886,1644323126,1726914158,1843922286,1973754846,2150009918,2185705214,2227254430,2272958078,2325220862,2386308798,2447666430,2512312830,2591771902,2686090046,2721489278,2762873566,2807207550,2860812926,2921068158,2982805918,3046299262,3125530238,3223828606,3299634910,3397945662,3523766590,3685626878,3802412158,3892963742,4007964286,4140023038,4301802894,4353035262,4402669758,4468565758,4543038398,4623235582,4703718302,4812658942,4870252462,4918603262,4979177598,5051794430,5131294142,5208637950,5311824446,5417085566,5531668478,5687199230,5905125374,5994130910,6130049918,6292111870,6454259966,6511693950,6557657342,6627134334,6711354558,6783327550,6864352254,6981069498,7025420798,7080077790,7139986942,7216432254,7290677502,7371380734,7479903230,7587832446,7711779838,7862048510,8061939038,8162263678,8306526206,8474813438,8619461006,8685561630,8760789710,8850582350,8948025502,9071651742,9161177438,9228085966,9303638638,9395527758,9492506974,9615980958,9744054862,9895087566,10114293374,10281167566,10433343182,10653121790,10775453054,10842557390,10919444286,11009632442,11110679230,11237120670,11316925998,11384145998,11462682430,11551709978,11653816638,11782646446,11908959582,12069510014,12295699166,12446854126,12608136558,12833418206,12952498526,13032337070,13145566030,13265349022,13423661694,13499446430,13593226558,13701644702,13834099258,13993034094,14170212190,14437379390,14630293854,14842274206,15057807694,15141962574,15242871374,15364705662,15504894878,15611934814,15704042190,15804196014,15919573406,16073691454,16240765646,16452625118,16710233774,16884935854,17176862078,17215603894,17258585182,17303254206,17360424358,17422199998,17486410102,17551614118,17639550718,17722977462,17763029142,17804494174,17855263934,17918593558,17977889982,18041337022,18106585854,18198168798,18284289526,18367885038,18485835742,18615395702,18795470574,18872432334,18979531502,19104196030,19268671710,19350923630,19399050166,19437364078,19491981662,19553127390,19614720734,19680465270,19760055998,19861793470,19899620222,19942681134,19987061878,20044608350,20106082542,20170567478,20235504286,20323087806,20412543454,20493638622,20607293166,20737611134,20900760286,21007126238,21091191662,21218992566,21358909406,21489286262,21548105086,21602797422,21679057582,21752232286,21825864414,21925471166,22021377726,22080210230,22125879702,22200563134,22281659702,22356124982,22448014014,22557785822,22658409526,22807219694,22975048670,23137195902,23253420398,23412868990,23622733270,23667688894,23723083630,23786464174,23862816446,23939034558,24026577246,24135755574,24197661294,24247789038,24308195502,24387400542,24466080190,24542864886,24655073150,24765866926,24880733054,25040142518,25239984350,25338697086,25480963438,25648845534,25801412526,25870863022,25950304814,26042674878,26147844958,26280619454,26359292654,26429274350,26516541790,26609197294,26720422622,26854607790,26988500734,27175525246,27394322158,27529325998,27718002398,27926620078,27994676606,28068039646,28155452094,28261305750,28387309246,28481882478,28550909294,28631286382,28723988830,28826709438,28958476894,29086202990,29247803118,29474647390,29628945790,29796393134,30021971710,30135226718,30224783710,30339128158,30471966558,30612794542,30702351038,30806055646,30921016158,31072465246,31222825838,31422041566,31691472350,31877409198,32122657534,32274015214,32358038238,32474054078,32598559614,32754351486,32834130782,32938511214,33053451710,33194456766,33358302574,33548930030,33827613358,33993340286,34234159838,34402271598,34478852990,34582463102,34707458302,34874652926,34962510846,35040669438,35148836414,35279374078,35455318014,35635388142,35933572094,36111657726,36366642686,36550183614,36627940094,36731348478,36855955678,37023919038,37111359982,37189024702,37298028990,37428101886,37606162158,37784923070,38086380734,38261129774,38518737918,38710685182,38816918414,38960687870,39143581182,39263897790,39372220078,39524068862,39719609854,39938236606,40287632886,40520103934,40822901758,40917855678,41050403582,41214339838,41377300670,41477198590,41613658814,41784813758,41989319790,42304641022,42565332990,42924148478,43059326078,43208355774,43426000574,43572662494,43716221694,43917735422,44168294638,44569395390,44848926206,45149203838,45282271806,45464968702,45668224190,45794132446,45966495230,46205374334,46506577086,46850674302,47247084990,47399939518,47621171966,47850033918,48024954046,48289671934,48651644926,49066618238,49444061694,49619601278,49873373886,50050386942,50257934334,50545601726,51007563966,51384453886,51596235262,51678664446,51788582462,51921871022,52086072998,52163216318,52258907006,52380885502,52531704574,52702421486,52924128254,53200967934,53396277694,53692999422,53768459646,53863457582,53981362590,54130618110,54261903870,54338366902,54445736702,54572941790,54744786430,54909351678,55172541630,55404840382,55639395838,55874078910,55975813854,56116340158,56305636094,56439490030,56547708094,56697474046,56896890366,57116481022,57466162542,57696982526,58004025822,58101623742,58242279870,58414602686,58565757374,58669303550,58821341110,59005055742,59222187006,59576011774,59802770430,60141950462,60272835006,60443280126,60675305150,60803291902,60971737854,61212489982,61500870142,61860761086,62256712190,62394081022,62555272702,62790283006,62924798718,63084571070,63316175614,63586260478,63965683438,64309578750,64541351422,64760769278,65004898174,65180420094,65442730750,65786268670,66215685822,66616062718,66792429054,67054476222,67240963582,67454373630,67755254142,68216889534,68623309822,68763799230,68829854718,68958882750,69056540094,69164751486,69283356030,69346253310,69459326590,69563958526,69657031678,69829104382,70066200030,70340193758,70542701278,70837896958,70916968830,70982863038,71118498686,71208627678,71338284798,71439075710,71504939902,71615173502,71718740318,71815874334,71992005118,72225212158,72500122846,72727006974,73016228958,73090357342,73217673758,73330360062,73451618046,73587794814,73665898686,73826521022,73919053758,74094283998,74369411550,74671283966,74964995966,75195170750,75272718206,75434826206,75515486078,75698942430,75771964190,75882540926,76010927486,76116152254,76322683262,76619881982,76920987518,77267631998,77391994462,77569996478,77713902270,77890016638,78017873662,78187448702,78400697214,78731284350,79090333310,79467309950,79569750910,79746506686,79930986430,80067402174,80216211038,80370376446,80610426750,81010761598,81347919358,81650560894,81841258238,82009554686,82210728894,82410892222,82578902910,82955913598,83385875454,83781967806,83953647358,84124757758,84331893310,84507590590,84684070782,85028396926,85461360638,85904384958,85971299710,86043994910,86177974142,86267551678,86436325822,86502457214,86567985022,86708937182,86785988542,86939694014,87104404990,87363534334,87609457246,87860947198,88074311614,88140480254,88254791294,88360855294,88458543038,88598208990,88665051070,88766285502,88887256958,88973906398,89152028158,89390787806,89666420478,89869483774,90163149822,90267002750,90378354558,90509095390,90627588030,90769082110,90847665918,91009049022,91104938686,91282909566,91572628990,91875573246,92154024830,92381402238,92466749310,92621121470,92717547006,92886417278,92961289086,93110558654,93219770238,93358849790,93596778238,93952928126,94226284286,94501565374,94615664734,94798216958,94999567038,95114484670,95297355710,95450332094,95728876542,96136489214,96475610622,96710135678,96867366654,97017945854,97213954430,97343195006,97517576126,97739609982,98075770750,98451118830,98806497214,98986283966,99161558782,99371138942,99566661502,99737685950,100128325374,100539268990,100955404734,101134015102,101309333374,101519244798,101714595710,101885726590,102276245758,102687429374,103102258686,103244242686,103453286142,103666296574,103845428222,104057168894,104461729278,104950265854,105285613310,105466372862,105677146814,105846447870,106048976638,106309533438,106777345022,107220849918,107488048318,107733105662,107980558078,108209773534,108501072894,109077167606,109564372350,109793519358,110059137662,110220901342,110458591678,110939848190,111517892094,111846992826,112208843422,112451567358,112835247614,113548836350,113942101758,114281772030,114534673150,114906430974,115553287678,116077895550,116486568958,116804364030,117378186750,118151675646,118477945854,118819268350,119254499070,120099634686,120362231550,120572239614,120810321790,120947538622,121169718526,121506232318,121985979390,122442114046,122595965950,122804125438,123017240734,123217792254,123459919614,123886434302,124372319742,124663669630,124905357054,125161459454,125395189502,125699989246,126271749630,126749412222,126981361406,127247026046,127443025662,127687733174,128213646334,128849280766,129096371966,129427859966,129703329534,130206793214,130965208062,131236540286,131570212606,131845463806,132341464574,133077892094,133446164222,133784682238,134186269694,134999916286,135496097534,135871434622,136205172222,136946761214,137450891166,137491562302,137532364118,137581736890,137642067222,137703851950,137762885246,137826740598,137917329334,137986836786,138026741678,138068273358,138117233502,138177855294,138237992110,138296374774,138361266622,138451855166,138535644374,138618538470,138729658238,138861273950,139049697386,139125290198,139218468478,139343418206,139495341694,139601741230,139647847210,139687005822,139733860558,139795051358,139858398910,139922716574,139989249062,140073389918,140137730518,140182775726,140221918638,140269795230,140330620318,140393563518,140458877790,140522860350,140607515414,140694441070,140778211814,140895309742,141025607038,141203034014,141279052750,141383466622,141508636086,141673153982,141762502494,141813104542,141873047470,141944145838,142016133590,142094857558,142197099390,142281753038,142339174326,142384867246,142453350206,142537689006,142610925782,142689718174,142810317774,142904935782,143044644782,143212480414,143383117438,143491476430,143647280182,143847997054,143919415102,143966904126,144028280782,144099750814,144179625822,144256581246,144360668990,144434931614,144492077518,144548460822,144620735070,144692973374,144766493782,144859621054,144967797222,145069382006,145224629886,145396141886,145555957614,145666412398,145828970334,146030673822,146096260558,146164155162,146240898126,146332999358,146442772382,146569891742,146635109966,146703815226,146782034638,146876843694,146986775134,147116928926,147249563854,147438448478,147654318430,147786735214,147975532382,148184899278,148248869278,148319517466,148397897566,148495187774,148606614494,148723403870,148789350350,148858686414,148941225598,149041569598,149151789502,149281848526,149418940030,149603565406,149819240398,149956463658,150141189758,150339170222,150426185534,150527805902,150637493950,150777996606,150896644014,150980600782,151080966558,151204864670,151346962334,151508275006,151729503614,151977183150,152153425870,152429494110,152540827598,152624083390,152740491070,152861031870,153012341662,153088407902,153185115966,153293766494,153426106782,153587666862,153763759054,154037984734,154222460542,154443341662,154631966134,154678618550,154718043582,154766688390,154830204182,154893560014,154959867710,155028914078,155122805014,155178513622,155227153510,155265401318,155319601102,155380506350,155442233182,155508171990,155587231422,155688566590,155768078566,155861290862,155986607742,156138983230,156270076782,156359910254,156476147310,156607555774,156772086998,156811710190,156852874670,156903893918,156967699750,157026376094,157089624406,157153681022,157246271294,157316288742,157362815462,157402279374,157450930894,157514478494,157577794774,157644131382,157712927438,157807045670,157892999678,157981288014,158109141222,158243114846,158394658158,158478995070,158591527246,158722510038,158903368958,158956717862,159010719078,159072661406,159151333182,159228045494,159313428286,159422562110,159486983998,159535237582,159597720478,159673574350,159754032246,159831762622,159938445118,160054978510,160164915006,160327411614,160529085654,160625803750,160765822894,160933910750,161076615070,161135415246,161192234862,161267011534,161339501910,161414657366,161516993982,161608777630,161667584926,161713666878,161791392638,161869541278,161943406806,162036585374,162146071390,162248344038,162403641526,162571816766,162731352550,162844011438,163007812446,163210100574,163278178254,163347894222,163431585998,163534809566,163648872126,163761188750,163830054094,163907264414,163995986542,164098887518,164226587550,164358873550,164507212766,164721772286,164897866190,165049621982,165268196526,165398554030,165466727230,165556551358,165641415582,165755404094,165893300942,165960987550,166029669278,166112159694,166211915582,166327929758,166459506526,166599483006,166785007070,167001252718,167143067054,167329966302,167524466142,167613164462,167716539086,167842967454,167986768798,168099404190,168185196446,168296778702,168422685022,168586184654,168754527870,168994328382,169213595502,169418342014,169662606766,169752133438,169856153438,169971638078,170122389310,170232120270,170324574014,170430463678,170557736766,170719346110,170874481358,171108466302,171339956062,171538687806,171805149374,171878449574,171967714622,172079314622,172217327294,172359321518,172437237414,172534692606,172650210806,172806809278,172973476590,173195929846,173468455662,173661522798,173953409166,174026294190,174116221162,174227798166,174367220926,174508348346,174585419190,174684394126,174798791102,174955957950,175121810598,175347907838,175618155246,175812983678,176102580274,176198659430,176322917278,176475786942,176651614014,176746419902,176878962606,177042955006,177249668846,177537296630,177818776950,178142652094,178312775278,178419509930,178568035774,178761125566,178858739630,178981759918,179126784702,179328857462,179560983470,179898527662,180156431614,180433866478,180566013246,180742307070,180952112766,181077093162,181244165374,181481530094,181773034238,182127960814,182528277758,182648522430,182801960766,183018900414,183165457310,183309053758,183512813246,183765646718,184163216574,184452054270,184757677486,184934825662,185206324670,185364311742,185577527710,185875369838,186336673022,186763046398,186965863854,187171498462,187410859950,187580146606,187831680446,188159118830,188600282622,188992720118,189073263054,189172858494,189292046014,189451839166,189562589102,189645611950,189755163942,189886549694,190061818998,190234705534,190525230782,190720133606,190969789694,191168859302,191248230630,191358838990,191486914774,191663562990,191739023014,191829292206,191943651006,192086682014,192267077870,192467205374,192765097470,192946422702,193251081470,193356746430,193483417518,193638865406,193823190118,193921095486,194054680230,194220198558,194428542070,194715514366,194998058622,195320401598,195494026422,195606112174,195761492118,195960439758,196055998270,196177669950,196336942334,196545787262,196805573886,197114275566,197402389942,197644665550,197788342078,197991325118,198176483006,198317970398,198517546686,198774353406,199179526894,199455145214,199768990638,199911045566,200096628414,200299159358,200438066606,200625082046,200875318910,201230765758,201542438526,201903030078,202076234670,202337140414,202520448942,202738657694,203038403502,203490922350,203886907070,204132765614,204350061822,204593643198,204774426542,205035650494,205388840190,205814785006,206170171674,206235399382,206323891838,206441965470,206532558462,206697127742,206762495318,206828468734,206965893534,207043323806,207178973022,207343525502,207603127670,207850964830,208109311190,208321263182,208386727838,208483802942,208603242174,208687718206,208848251094,208913671998,208984269790,209118633886,209196416830,209351310974,209516999518,209780767998,210017888638,210269027966,210489465054,210567663422,210728091486,210819596094,210992038194,211066176598,211193483070,211306219702,211427551934,211631095422,211936978686,212242284158,212600899166,212673891670,212783762238,212912766590,213017774870,213171332022,213248644214,213410718806,213491679134,213675095254,213948388822,214247374078,214532487678,214784174494,214896892574,215078788542,215286445982,215382777758,215558160222,215706066782,215971904350,216386843486,216719892318,216963773646,217103216542,217257384286,217449533722,217563709166,217738247422,217929775006,218243415902,218593244366,219010629246,219155957566,219359739710,219584076058,219719229342,219920469918,220170198398,220654301022,221044407678,221283604830,221486012318,221695868734,221837344574,222039640958,222270324350,222676844158,223138479742,223373957838,223440610870,223554281086,223664026526,223767830430,223897501310,223963905854,224079521566,224186027574,224282287966,224458505966,224693671126,224967669206,225195179646,225487160406,225554008278,225622628046,225760026430,225839234974,225996367550,226073231166,226139610942,226289884030,226368030934,226503480222,226668845950,226928890998,227178211806,227436857814,227661610910,227743631542,227906666302,227995697054,228171977942,228247159894,228378272414,228505700566,228621384670,228836416894,229176786782,229460716126,229784620958,229859479454,229992254230,230117434974,230251186966,230364156766,230458511038,230602729374,230700787518,230902158710,231195093462,231480180574,231777238270,232000338510,232154947486,232307736190,232503619390,232633090974,232806731582,233027469038,233361129182,233740216942,234089810334,234208140670,234387226430,234590906046,234705892190,234885967774,235049123454,235326444414,235729092334,236068912766,236313927582,236525663070,236738487998,236877774654,237096937374,237339287166,237802420990,238210710782,238462982046,238673301310,238886738590,239026110270,239244574558,239487131262,239951804158,240359071358,240598927542,240800378622,241055895422,241168158398,241387486910,241665785086,242171308270,242669317822,242781300462,243004025246,243233223422,243375491766,243581111998,243926030334,244402123774,244855350326,245084169918,245350212250,245505776574,245745548790,246229040382,246806816510,247075811134,247329357246,247569017334,247800726462,248102005110,248673410686,249171492222,249448595134,249739967934,250030804670,250663532286,251289323966,251551691486,251860054750,252136483230,252665478398,253406564030,253715087038,254049206078,254445812478,255259835134,255740952382,256122227582,256435322110,257162690174,257739087550,257905573502,258111853470,258313214398,258516076214,258776765558,259236199166,259690561014,259942585246,260152600254,260393157534,260525327126,260747442326,261059869438,261562301694,262030491326,262255344574,262518602686,262697826110,262937340822,263425817086,264017410814,264275888830,264519794366};
void qwq()
{
	for(int i=B;i>=1;i--) if(buc[i]) for(int j=i+1;j<=B;j++) if(buc[j]) buc[gc[i][j]]=1;
}
void print()
{
	int sz=0;
	for(int i=1;i<=B;i++) if(buc[i]) sz++;
	cout<<sz<<" ";
	for(int i=1;i<=B;i++) if(buc[i]) cout<<i<<" ";
	cout<<"\n";
}
ll gethash()
{
	ll re=0;
	for(int i=1;i<=B;i++) re+=(1LL<<i)*buc[i];
	return re;
}
void solve()
{
	int K;
	cin>>K;
	memset(buc,0,sizeof(buc)); 
	int idx=K/1000000;
	for(int i=1;i<=B;i++) if(tab[idx]&(1LL<<i)) buc[i]=1;
	K%=1000000;
	while(K--)
	{
		for(int i=1;i<=B;i++) if(!buc[i])
		{
			buc[i]=1;
			for(int j=1;j<i;j++) buc[j]=0;
			qwq();
			break;
		}
	}
	print();
}
signed main()
{
//	freopen("table.txt","w",stdout);
	for(int i=0;i<=B;i++) for(int j=0;j<=B;j++) gc[i][j]=__gcd(i,j);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}

Compilation message (stderr)

Main.cpp:30:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   30 | const int INF=1e18;
      |               ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16