Submission #1037383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037383		andrei_c1	Present (RMI21_present)	C++17	100 / 100	1857 ms	600 KiB

Main

/**
* user:  chertes-cab
* fname: Andrei
* lname: Chertes
* task:  Present
* score: 29.0
* date:  2021-12-16 08:14:57.934784
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int kBits = 37;
const int kB = 1e6;
const int kLim = 1e8;

int g[kBits][kBits];
const ll v[] = {0,16875563,37996375,58218911,85307503,115369951,145427647,177042815,216122559,265554303,284435415,306146687,325960347,352927583,382573487,413083375,444714719,482943919,531634543,572835271,616833207,678626151,752552943,822161563,863457079,921961143,986877423,1075004959,1092852607,1113627215,1136479039,1162610431,1193154399,1223833215,1256156415,1295885951,1343045023,1360744639,1381436783,1403603775,1430406463,1460534079,1491402959,1523149631,1562765119,1611914303,1649817455,1698972831,1761883295,1842813439,1901206079,1946481871,2003982143,2070011519,2150901447,2176517631,2201334879,2234282879,2271519199,2311617791,2351859151,2406329471,2435126231,2459301631,2489588799,2525897215,2565647071,2604318975,2655912223,2708542783,2765834239,2843599615,2952562687,2997065455,3065024959,3146055935,3227129983,3255846975,3278828671,3313567167,3355677279,3391663775,3432176127,3490534749,3512710399,3540038895,3569993471,3608216127,3645338751,3685690367,3739951615,3793916223,3855889919,3931024255,4030969519,4081131839,4153263103,4237406719,4309730503,4342780815,4380394855,4425291175,4474012751,4535825871,4580588719,4614042983,4651819319,4697763879,4746253487,4807990479,4872027431,4947543783,5057146687,5140583783,5216671591,5326560895,5387726527,5421278695,5459722143,5504816221,5555339615,5618560335,5658462999,5692072999,5731341215,5775854989,5826908319,5891323223,5954479791,6034755007,6147849583,6223427063,6304068279,6416709103,6476249263,6516168535,6572783015,6632674511,6711830847,6749723215,6796613279,6850822351,6917049629,6996517047,7085106095,7218689695,7315146927,7421137103,7528903847,7570981287,7621435687,7682352831,7752447439,7805967407,7852021095,7902098007,7959786703,8036845727,8120382823,8226312559,8355116887,8442467927,8588431039,8607801947,8629292591,8651627103,8680212179,8711099999,8743205051,8775807059,8819775359,8861488731,8881514571,8902247087,8927631967,8959296779,8988944991,9020668511,9053292927,9099084399,9142144763,9183942519,9242917871,9307697851,9397735287,9436216167,9489765751,9552098015,9634335855,9675461815,9699525083,9718682039,9745990831,9776563695,9807360367,9840232635,9880027999,9930896735,9949810111,9971340567,9993530939,10022304175,10053041271,10085283739,10117752143,10161543903,10206271727,10246819311,10303646583,10368805567,10450380143,10503563119,10545595831,10609496283,10679454703,10744643131,10774052543,10801398711,10839528791,10876116143,10912932207,10962735583,11010688863,11040105115,11062939851,11100281567,11140829851,11178062491,11224007007,11278892911,11329204763,11403609847,11487524335,11568597951,11626710199,11706434495,11811366635,11833844447,11861541815,11893232087,11931408223,11969517279,12013288623,12067877787,12098830647,12123894519,12154097751,12193700271,12233040095,12271432443,12327536575,12382933463,12440366527,12520071259,12619992175,12669348543,12740481719,12824422767,12900706263,12935431511,12975152407,13021337439,13073922479,13140309727,13179646327,13214637175,13258270895,13304598647,13360211311,13427303895,13494250367,13587762623,13697161079,13764662999,13859001199,13963310039,13997338303,14034019823,14077726047,14130652875,14193654623,14240941239,14275454647,14315643191,14361994415,14413354719,14479238447,14543101495,14623901559,14737323695,14814472895,14898196567,15010985855,15067613359,15112391855,15169564079,15235983279,15306397271,15351175519,15403027823,15460508079,15536232623,15611412919,15711020783,15845736175,15938704599,16061328767,16137007607,16179019119,16237027039,16299279807,16377175743,16417065391,16469255607,16526725855,16597228383,16679151287,16774465015,16913806679,16996670143,17117079919,17201135799,17239426495,17291231551,17353729151,17437326463,17481255423,17520334719,17574418207,17639687039,17727659007,17817694071,17966786047,18055828863,18183321343,18275091807,18313970047,18365674239,18427977839,18511959519,18555679991,18594512351,18649014495,18714050943,18803081079,18892461535,19043190367,19130564887,19259368959,19355342591,19408459207,19480343935,19571790591,19631948895,19686110039,19762034431,19859804927,19969118303,20143816443,20260051967,20411450879,20458927839,20525201791,20607169919,20688650335,20738599295,20806829407,20892406879,20994659895,21152320511,21282666495,21462074239,21529663039,21604177887,21713000287,21786331247,21858110847,21958867711,22084147319,22284697695,22424463103,22574601919,22641135903,22732484351,22834112095,22897066223,22983247615,23102687167,23253288543,23425337151,23623542495,23699969759,23810585983,23925016959,24012477023,24144835967,24325822463,24533309119,24722030847,24809800639,24936686943,25025193471,25128967167,25272800863,25503781983,25692226943,25798117631,25839332223,25894291231,25960935511,26043036499,26081608159,26129453503,26190442751,26265852287,26351210743,26462064127,26600483967,26698138847,26846499711,26884229823,26931728791,26990681295,27065309055,27130951935,27169183451,27222868351,27286470895,27372393215,27454675839,27586270815,27702420191,27819697919,27937039455,27987906927,28058170079,28152818047,28219745015,28273854047,28348737023,28448445183,28558240511,28733081271,28848491263,29002012911,29050811871,29121139935,29207301343,29282878687,29334651775,29410670555,29502527871,29611093503,29788005887,29901385215,30070975231,30136417503,30221640063,30337652575,30401645951,30485868927,30606244991,30750435071,30930380543,31128356095,31197040511,31277636351,31395141503,31462399359,31542285535,31658087807,31793130239,31982841719,32154789375,32270675711,32380384639,32502449087,32590210047,32721365375,32893134335,33107842911,33308031359,33396214527,33527238111,33620481791,33727186815,33877627071,34108444767,34311654911,34381899615,34414927359,34479441375,34528270047,34582375743,34641678015,34673126655,34729663295,34781979263,34828515839,34914552191,35033100015,35170096879,35271350639,35418948479,35458484415,35491431519,35559249343,35604313839,35669142399,35719537855,35752469951,35807586751,35859370159,35907937167,35996002559,36112606079,36250061423,36363503487,36508114479,36545178671,36608836879,36665180031,36725809023,36793897407,36832949343,36913260511,36959526879,37047141999,37184705775,37335641983,37482497983,37597585375,37636359103,37717413103,37757743039,37849471215,37885982095,37941270463,38005463743,38058076127,38161341631,38309940991,38460493759,38633815999,38695997231,38784998239,38856951135,38945008319,39008936831,39093724351,39200348607,39365642175,39545166655,39733654975,39784875455,39873253343,39965493215,40033701087,40108105519,40185188223,40305213375,40505380799,40673959679,40825280447,40920629119,41004777343,41105364447,41205446111,41289451455,41477956799,41692937727,41890983903,41976823679,42062378879,42165946655,42253795295,42342035391,42514198463,42730680319,42952192479,42985649855,43021997455,43088987071,43133775839,43218162911,43251228607,43283992511,43354468591,43392994271,43469847007,43552202495,43681767167,43804728623,43930473599,44037155807,44070240127,44127395647,44180427647,44229271519,44299104495,44332525535,44383142751,44443628479,44486953199,44576014079,44695393903,44833210239,44934741887,45081574911,45133501375,45189177279,45254547695,45313794015,45384541055,45423832959,45504524511,45552469343,45641454783,45786314495,45937786623,46077012415,46190701119,46233374655,46310560735,46358773503,46443208639,46480644543,46555279327,46609885119,46679424895,46798389119,46976464063,47113142143,47250782687,47307832367,47399108479,47499783519,47557242335,47648677855,47725166047,47864438271,48068244607,48237805311,48355067839,48433683327,48508972927,48606977215,48671597503,48758788063,48869804991,49037885375,49225559415,49403248607,49493141983,49580779391,49685569471,49783330751,49868842975,50064162687,50269634495,50477702367,50567007551,50654666687,50759622399,50857297855,50942863295,51138122879,51343714687,51551129343,51622121343,51726643071,51833148287,51922714111,52028584447,52230864639,52475132927,52642806655,52733186431,52838573407,52923223935,53024488319,53154766719,53388672511,53610424959,53744024159,53866552831,53990279039,54104886767,54250536447,54538583803,54782186175,54896759679,55029568831,55110450671,55229295839,55469924095,55758946047,55923496413,56104421711,56225783679,56417623807,56774418175,56971050879,57140886015,57267336575,57453215487,57776643839,58038947775,58243284479,58402182015,58689093375,59075837823,59238972927,59409634175,59627249535,60049817343,60181115775,60286119807,60405160895,60473769311,60584859263,60753116159,60992989695,61221057023,61297982975,61402062719,61508620367,61608896127,61729959807,61943217151,62186159871,62331834815,62452678527,62580729727,62697594751,62849994623,63135874815,63374706111,63490680703,63623513023,63721512831,63843866587,64106823167,64424640383,64548185983,64713929983,64851664767,65103396607,65482604031,65618270143,65785106303,65922731903,66170732287,66538946047,66723082111,66892341119,67093134847,67499958143,67748048767,67935717311,68102586111,68473380607,68725445583,68745781151,68766182059,68790868445,68821033611,68851925975,68881442623,68913370299,68958664667,68993418393,69013370839,69034136679,69058616751,69088927647,69118996055,69148187387,69180633311,69225927583,69267822187,69309269235,69364829119,69430636975,69524848693,69562645099,69609234239,69671709103,69747670847,69800870615,69823923605,69843502911,69866930279,69897525679,69929199455,69961358287,69994624531,70036694959,70068865259,70091387863,70110959319,70134897615,70165310159,70196781759,70229438895,70261430175,70303757707,70347220535,70389105907,70447654871,70512803519,70601517007,70639526375,70691733311,70754318043,70836576991,70881251247,70906552271,70936523735,70972072919,71008066795,71047428779,71098549695,71140876519,71169587163,71192433623,71226675103,71268844503,71305462891,71344859087,71405158887,71452467891,71522322391,71606240207,71691558719,71745738215,71823640091,71923998527,71959707551,71983452063,72014140391,72049875407,72089812911,72128290623,72180334495,72217465807,72246038759,72274230411,72310367535,72346486687,72383246891,72429810527,72483898611,72534691003,72612314943,72698070943,72777978807,72833206199,72914485167,73015336911,73048130279,73082077581,73120449063,73166499679,73221386191,73284945871,73317554983,73351907613,73391017319,73438421847,73493387567,73558464463,73624781927,73719224239,73827159215,73893367607,73987766191,74092449639,74124434639,74159758733,74198948783,74247593887,74303307247,74361701935,74394675175,74429343207,74470612799,74520784799,74575894751,74640924263,74709470015,74801782703,74909620199,74978231829,75070594879,75169585111,75213092767,75263902951,75318746975,75388998303,75448322007,75490300391,75540483279,75602432335,75673481167,75754137503,75864751807,75988591575,76076712935,76214747055,76270413799,76312041695,76370245535,76430515935,76506170831,76544203951,76592557983,76646883247,76713053391,76793833431,76881879527,77018992367,77111230271,77221670831,77315983067,77339309275,77359021791,77383344195,77415102091,77446780007,77479933855,77514457039,77561402507,77589256811,77613576755,77632700659,77659800551,77690253175,77721116591,77754085995,77793615711,77844283295,77884039283,77930645431,77993303871,78069491615,78135038391,78179955127,78238073655,78303777887,78386043499,78405855095,78426437335,78451946959,78483849875,78513188047,78544812203,78576840511,78623135647,78658144371,78681407731,78701139687,78725465447,78757239247,78788897387,78822065691,78856463719,78903522835,78946499839,78990644007,79054570611,79121557423,79197329079,79239497535,79295763623,79361255019,79451684479,79478358931,79505359539,79536330703,79575666591,79614022747,79656714143,79711281055,79743491999,79767618791,79798860239,79836787175,79877016123,79915881311,79969222559,80027489255,80082457503,80163705807,80264542827,80312901875,80382911447,80466955375,80538307535,80567707623,80596117431,80633505767,80669750955,80707328683,80758496991,80804388815,80833792463,80856833439,80895696319,80934770639,80971703403,81018292687,81073035695,81124172019,81201820763,81285908383,81365676275,81422005719,81503906223,81605050287,81639089127,81673947111,81715792999,81767404783,81824436063,81880594375,81915027047,81953632207,81997993271,82049443759,82113293775,82179436775,82253606383,82360886143,82448933095,82524810991,82634098263,82699277015,82733363615,82778275679,82820707791,82877702047,82946650471,82980493775,83014834639,83056079847,83105957791,83163964879,83229753263,83299741503,83392503535,83500626359,83571533527,83664983151,83762233071,83806582231,83858269543,83921483727,83993384399,84049702095,84092598223,84148389351,84211342511,84293092327,84377263935,84497164191,84606797751,84709171007,84831303383,84876066719,84928076719,84985819039,85061194655,85116060135,85162287007,85215231839,85278868383,85359673055,85437240679,85554233151,85669978031,85769343903,85902574687,85939224787,85983857311,86039657311,86108663647,86179660759,86218618707,86267346303,86325105403,86403404639,86486738295,86597964923,86734227831,86830761399,86976704583,87013147095,87058110581,87113899083,87183610463,87254174173,87292709595,87342197063,87399395551,87477978975,87560905299,87673953919,87809077623,87906491839,88051290137,88099329715,88161458639,88237893471,88325807007,88373209951,88439481303,88521477503,88624834423,88768648315,88909388475,89071326047,89156387639,89209754965,89284017887,89380562783,89429369815,89490879959,89563392351,89664428731,89780491735,89949263831,90078215807,90216933239,90283006623,90371153535,90476056383,90538546581,90622082687,90740765047,90886517119,91063980407,91264138879,91324261215,91400980383,91509450207,91582728655,91654526879,91756406623,91882823359,92081608287,92226027135,92378838743,92467412831,92603162335,92682155871,92788763855,92937684919,93168336511,93381523199,93482931927,93585749231,93705429975,93790073303,93915840223,94079559415,94300141311,94496360059,94536631527,94586429247,94646023007,94725919583,94781294551,94822805975,94877581971,94943274847,95030909499,95117352767,95262615391,95360066803,95484894847,95584429651,95624115315,95679419495,95743457387,95831781495,95869511507,95914646103,95971825503,96043341007,96133538935,96233602687,96382548735,96473211351,96625540735,96678373215,96741708759,96819432703,96911595059,96960547743,97027340115,97110099279,97214271035,97357757183,97499029311,97660200799,97747013211,97803056087,97880746059,97980219879,98027999135,98088834975,98168471167,98272893631,98402786943,98557137783,98701194971,98822332775,98894171039,98995662559,99088241503,99158985199,99258773343,99387176703,99589763447,99727572607,99884495319,99955522783,100048314207,100149579679,100219033303,100312541023,100437659455,100615382879,100771219263,100951515039,101038117335,101168570207,101260224471,101369328847,101519201751,101745461175,101943453535,102066382807,102175030911,102296821599,102387213271,102517825247,102694420095,102907392503,103085085837,103117699691,103161945919,103220982735,103266279231,103348563871,103381247659,103414234367,103482946767,103521661903,103589486511,103671762751,103801563835,103925482415,104054655595,104160631591,104193363919,104241901471,104301621087,104343859103,104424125547,104456835999,104492134895,104559316943,104598208415,104675655487,104758499759,104890383999,105008944319,105134513983,105244732527,105283831711,105364045743,105409798047,105496019097,105533088299,105596741535,105653109851,105713775967,105815547711,105968489343,106121142079,106300449583,106336945835,106391881119,106456383295,106508887435,106585666011,106624322107,106705359403,106745839567,106837547627,106974194411,107123687039,107266243839,107392087247,107448446287,107539394271,107643222991,107691388879,107779080111,107853033391,107985952175,108193421743,108359946159,108481886823,108551608271,108628692143,108724766861,108781854583,108869123711,108964887503,109121707951,109296622183,109505314623,109577978783,109679869855,109792038029,109859614671,109960234959,110085099199,110327150511,110522203839,110641802415,110743006159,110847934367,110918672287,111019820479,111135162175,111338422079,111569239871,111686978919,111720305435,111777140543,111832013263,111883915215,111948750655,111981952927,112039760783,112093013787,112141143983,112229252983,112346835563,112483834603,112597589823,112743580203,112777004139,112811314023,112880013215,112919617487,112998183775,113036615583,113069805471,113144942015,113184015467,113251740111,113334422975,113464445499,113589105903,113718428907,113830805455,113871815771,113953333151,113997848527,114085988971,114123579947,114189136207,114252850283,114310692335,114418208447,114588393391,114730358063,114892310479,114929739727,114996127115,115058717487,115125593483,115182078383,115229255519,115301364687,115350393759,115451079355,115597546731,115740090287,115888619135,116000169255,116077473743,116153868095,116251809695,116316545487,116403365791,116513734519,116680564591,116870108471,117044905167,117104070335,117193613215,117295453023,117352946095,117442983887,117524561727,117663222207,117864546167,118034456383,118156963791,118262831535,118369243999,118438887327,118548468687,118669643583,118901210495,119105355391,119231491023,119336650655,119443369295,119513055135,119622287279,119743565631,119975902079,120179535679,120299463771,120400189311,120527947711,120584079199,120693743455,120832892543,121085654135,121334658911,121390650231,121502012623,121616611711,121687745883,121790555999,121963015167,122201061887,122427675163,122542084959,122675106125,122752888287,122872774395,123114520191,123403408255,123537905567,123664678623,123784508667,123900363231,124051002555,124336705343,124585746111,124724297567,124869983967,125015402335,125331766143,125644661983,125775845743,125930027375,126068241615,126332739199,126703282015,126857543519,127024603039,127222906239,127629917567,127870476191,128061113791,128217661055,128581345087,128869543775,128952786751,129055926735,129156607199,129258038107,129388382779,129618099583,129845280507,129971292623,130076300127,130196578767,130262663563,130373721163,130529934719,130781150847,131015245663,131127672287,131259301343,131348913055,131468670411,131712908543,132008705407,132137944415,132259897183,132379053659,132500709087,132664053567,132966010687,133190465999,133342346495,133486124303,133674301951,134000814463,134259691095,134409578335,134557080959,134741644639,135066713727,135343640415,135544689503,135711518559,136000831103,136386930527,136554041183,136737076575,136961105599,137419225599};

ll next(ll mask) {
	ll nmask = mask + 1;
	for(int i = kBits - 1; i >= 0; i--) {
		if(nmask >> i & 1) {
			for(int j = i - 1; j >= 0; j--) {
				if(nmask >> j & 1) {
					int gcd = g[i][j];
					if(!(nmask >> gcd & 1)) {
						nmask |= 1ll << gcd;
					}
				}
			}
		}
	}
	return nmask;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	for(int i = 0; i < kBits; i++) {
		for(int j = 0; j < kBits; j++) {
			g[i][j] = __gcd(i + 1, j + 1) - 1;
		}
	}
	int t;
	cin >> t;
	while(t--) {
		int k;
		cin >> k;
		ll mask = v[k / kB];
		int extra = k % kB;
		while(extra) {
			mask = next(mask);
			extra--;
		}
		cout << __builtin_popcountll(mask) << " ";
		for(int i = 0; i < kBits; i++) {
			if(mask >> i & 1) {
				cout << i + 1 << " ";
			}
		}
		cout << '\n';
	}
	return 0;
}

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