hdu6889 Graph Theory Class
传送门
题意
有一个(n)个节点的完全图，节点编号为([1,n])，每条边的权值是(lcm(u+1,v+1))，其中(u,v)是这条边所连接的节点编号，计算最小生成树的权值模(k)的值
其中(1leq nleq 1e10)
题解
分段打表+区间素数筛
由于(uin [1,n])，所以((u+1)in [2,n+1])
设([2,n+1])为点的权值
最小生成树的构成：
对于点权为合数的点，连接它的一个因子，边权为它本身的值
对于点权为质数的点，连接(2)，边权为它本身的值乘(2)
所以最终结果为([3,n+1])中所有数的和加上所有质数的和
([3,n+1])中所有数的和为(frac{(n+4)*(n-1)}{2})
由于(1leq nleq 1e10)，所以分段打表质数的前缀和，区间素数筛筛出余下部分的质数
打表代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=2e8+10;
int prime[maxn],cnt;
LL ans[100010];
bool is_prime1[maxn],is_prime2[maxn];
void segment_sieve(LL a,LL b){
LL t=sqrt(b),n=b-a+1;
for(int i=2;i<=t;i++) is_prime1[i]=1;
for(int i=0;i<n;i++) is_prime2[i]=1;
for(int i=2;i<=t;i++){
if(is_prime1[i]){
for(int j=2*i;j<=t;j+=i) is_prime1[j]=0;
for(LL j=max((LL)2,(a+i-1)/i)*i;j<=b;j+=i){
is_prime2[j-a]=0;
}
}
}
LL sum=0;
for(LL i=0;i<n;i++){
if(is_prime2[i] && i+a>2) sum+=i+a;
if((a+i)%5000000==0){
ans[cnt++]=sum;
sum=0;
}
}
}
int main(){
freopen("data.out","w",stdout);
for(int i=0;i<102;i+=2){
segment_sieve(1ll*i*1e8+1,1ll*(i+2)*1e8);
}
for(int i=1;i<cnt;i++) ans[i]+=ans[i-1];
for(int i=0;i<cnt;i++) printf("%lld,",ans[i]);
}
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int len=5e6;
int prime[len+10],T;
bool is_prime1[len+10],is_prime2[len+10];
LL n,mod;
LL sum[]={838596693106,3203324994354,7026422648069,12272577818050,18915756212152,26942805919964,36331032004948,47088408550137,59179138492165,72619548630275,87374652934561,103468900363398,120870704344593,139601928199357,159628664325065,180946446237949,203579320480630,227485624300929,252718831683406,279209790387274,307011790722809,336102842056832,366403360189039,398010087395243,430900704773071,465076136040030,500489851895134,537166405508374,575127619405622,614333144695289,654769646519668,696491836941977,739476828720977,783713993345744,829199781436379,875990973971372,923916471943999,973132625143756,1023588368264786,1075207199997332,1128168190846830,1182357709860115,1237744437272787,1294353294416651,1352277946409028,1411359454893924,1471679895005690,1533317147057479,1596152812247037,1660170771905891,1725441857925940,1791887745621003,1859592431642414,1928499553076515,1998658456125741,2070037758014650,2142586603819210,2216411905082804,2291449950947755,2367646772295460,2445116662950711,2523866600166348,2603717273255594,2684731276904015,2767011287349449,2850568515870882,2935247493510622,3021127003743002,3108373747527408,3196703482711199,3286242600796926,3376958413069619,3468860344681501,3562055899616522,3656429144165189,3752170121640032,3848975369208103,3946916107520393,4046052035118002,4146437503168145,4247973982198045,4350713797609464,4454709882553476,4559774703609066,4666257168341129,4773791241429155,4882518171415296,4992380574480392,5103660030211838,5215984059716387,5329474402629788,5444170553697013,5560083612668704,5677213796090293,5795391148848291,5915050127319651,6035683359006360,6157522951818011,6280519462828934,6404774487532574,6529975494013612,6656459291988151,6784009201028303,6913154895394660,7043215380181463,7174611476852483,7307068680766505,7440871802567462,7575557005150542,7711724083073571,7849095929181419,7987442685136051,8127057348437643,8267758615241163,8409747835417459,8552894678625830,8697168034179374,8842685674255563,8989434496383099,9137303389808022,9286588325999822,9436619750436323,9588046374360158,9740394371660821,9894119103348378,10049045128993918,10205006310178161,10362240272645795,10520491715461550,10680189372387878,10840962314255294,11002956586881427,11166032950283105,11330234145394920,11495688364383791,11662231483112902,11829837322392089,11998965645219224,12169128722192323,12340337443955706,12512796036181269,12686473825403156,12861132463031063,13036925941489951,13214274324956464,13392262072650237,13571569117886221,13752278206678608,13934075103695843,14116726304047226,14300642624577703,14485949887359826,14672209696559450,14859851769032720,15048628834907376,15238436132857963,15429696383699911,15622126205971630,15815390301334045,16010026481858290,16205846194186762,16402872774962456,16600787304310155,16800034584560737,17000220853732503,17201728442251763,17404503105412154,17608378509778585,17813362872031218,18019518580817003,18226760108857419,18434940123089655,18644515034935600,18855372238489043,19067373539343476,19280161081618122,19494165698103052,19709431503921551,19925910953259061,20143329357815160,20361996210568231,20582564936558670,20803946549761906,21026363464193700,21249666302385213,21473923117873880,21699807141375913,21926452565299115,22154562782502268,22383876593236982,22614228689489147,22845949677423409,23078727011839552,23312509002287459,23547410407871503,23783220704190491,24020749273798064,24259101990397720,24498697181268944,24739512092254533,24981263267412899,25224373813632748,25468662008430904,25713946377217900,25960433169533849,26207992824418785,26456552420804153,26706754086711121,26957762703331907,27209541722648037,27462853781818238,27717214454853886,27972973815596372,28229941285041849,28487902785901999,28746633469521956,29007318002192667,29268683359350869,29531265596670921,29795030058292247,30059889665572254,30325909420256060,30592740448001342,30860943104541282,31129920491356528,31400361110845703,31671479849061780,31944228867615707,32217374333476300,32492526353208086,32769086923311640,33046298432422936,33325079843702086,33604762596372509,33885705393577865,34167504798926529,34450026762521150,34734183764128588,35019342731885959,35305948769039210,35592988027980142,35882007747879060,36171865421711508,36463125817968832,36755023230290233,37047794688673149,37342212297536940,37637743962269284,37934116455248759,38232425938401253,38531634260649018,38831423995263185,39132652598718800,39435769460487715,39738904547144347,40043602459363976,40349110269823549,40656142728840931,40964162988744061,41272831981428624,41583248706147170,41895354366411612,42207693946877897,42521191094232577,42835808411313401,43151655002891555,43469150516234733,43787311707867843,44107022272991969,44427481937478529,44749332774947504,45072355983106101,45396516460208515,45721274438833858,46047238596859183,46374219971298056,46702531549984373,47032003347685126,47363106257229270,47694811567934918,48027196753531371,48361320057757901,48696708759595576,49033120405522545,49370466110643167,49709152185224623,50048823620740611,50389295265403043,50731292845352610,51074813235175958,51418787210539315,51764393739028432,52111125900947092,52458146887383617,52806983725681100,53157539231984817,53508371734444672,53860855268765416,54214901624248317,54569260920066581,54924629470415599,55281407190764320,55638843452751567,55998032929881001,56357921612690335,56719837432633244,57081619756417817,57444959050696465,57809246974753942,58175194938893997,58542185433750116,58910104427451710,59278146681458871,59648482584577232,60019538016648133,60392539636429630,60766140893116517,61140741768689646,61516271935544636,61893367909604124,62271577383273752,62650580713198338,63030571472710109,63411532609492656,63794411110747539,64178138379761452,64563452401908023,64949487821851694,65335986791046574,65724186881400064,66112843040197177,66502998128368971,66894539909702523,67287233912661256,67680899867920424,68076061856016158,68472185095257655,68869791015785909,69267616235854795,69666709926131676,70067349040331708,70469651531118493,70871957089786990,71276338909159528,71681334570523729,72087286947763759,72493849500064525,72902153727155658,73311571446694958,73722162212208841,74134041920369129,74546987923434239,74960752804433775,75375777478591382,75791565119493637,76209171112782059,76627689579102738,77047078273475857,77468244306469901,77890574031485655,78313229567798846,78737263845348273,79162023090209275,79588083222416710,80015283253337075,80443585352169718,80873394884696846,81304020375439524,81735841737351389,82168230280536611,82602076480203408,83037397571998371,83473578095258986,83910760214626622,84349311528750446,84788864492747772,85228900818425243,85671208660856558,86114116160279127,86558685854397367,87003939570457819,87449888385252214,87897159110265623,88345480153813488,88794762897199655,89245557277965150,89697599733683624,90150383289103863,90604493278225987,91059902452946686,91516777191273285,91974156813784404,92432504853977131,92892130973265084,93353471587218268,93815251421286029,94278539620186680,94742644961610148,95208095387368099,95673602693282038,96142239255498064,96611162807637860,97081394265302831,97552294636583807,98023769740245094,98496351161228854,98971292015537593,99446101419800688,99922243366747969,100400140238200840,100878719448635741,101357604379933816,101838804765946131,102320400301626323,102803450963277595,103287492085780875,103772866446608158,104259323328131245,104746928367197298,105235160736446015,105725856858011524,106216769704188362,106709510206025012,107202508908386543,107695996769377116,108190629937919787,108686225464197214,109183107045037339,109682277177617904,110182313391179756,110683471329131142,111185107495098784,111688175781164289,112192221158715034,112697592105469342,113204629088682719,113711141765004818,114219903890568775,114729767839394942,115240288380418389,115751182199144992,116264584560095786,116778543662708276,117293851192104076,117809739754271185,118327767436163471,118845964558062368,119365825197475150,119886262320728907,120408578391415346,120932000212559536,121455713456251142,121981710401026731,122508577673401385,123037622612728574,123565309586840470,124094052574952463,124625907112966782,125157962235452057,125691092387226311,126224922549232755,126759358129814237,127296748520136672,127832660548280758,128371784289534247,128910758528205085,129451392853873300,129993311787175941,130535607365601524,131079353900023830,131624686789705094,132170632029765198,132717475536635286,133266425605302705,133815884846638378,134366319002769386,134918368679671740,135471017855232222,136024958000153396,136579773679267082,137134948398372066,137692351919076542,138250568318765561,138810101731760730,139370755916822528,139932719197291597,140495108252920169,141059638781858921,141624334995614605,142189584004778625,142756957448869968,143325292850665592,143893888811568992,144464838590904360,145037430106404888,145609821707080544,146184679104492638,146758329070018573,147334406164674815,147910767168788966,148488594975753484,149068486835261109,149649434973406804,150230977425625842,150813366904781576,151397639230259146,151983123105600012,152569077591069302,153155687446248282,153744713250999333,154333740955509356,154924871327699434,155516238113058377,156109530889182859,156703467496797896,157298148236796934,157894134975496291,158491014727162261,159089228447172987,159688630098986230,160288410430913195,160888735109394135,161491200695358046,162094872050906649,162699714558755801,163304801329588147,163912076332489871,164519181970704097,165127746906382938,165737508762827720,166348655662936778,166961333546829993,167574478495266822,168188854718038989,168804812700046265,169421547921363913,170038862845789936,170658554727653315,171278424903706568,171899866511374887,172522086988583714,173145583369474991,173770171703325222,174395816566482112,175021616132318796,175648065208169495,176277053822340121,176906742260801456,177537198398826490,178168570923322495,178801689675148761,179435996649277803,180071040077667167,180707800605956008,181345941097714492,181984902254934541,182624008857716745,183265462528106753,183906804747400947,184549994330138133,185194729011646288,185840215128592975,186486460956785569,187134066517584718,187783212964213048,188433020790608719,189083198764800365,189734504376991770,190386775368511967,191041543591686610,191697065425211778,192353272828145324,193011266886141631,193669696484346039,194329337309138345,194989602795271001,195651329601727994,196313840517787377,196976876527278253,197642104332732212,198308602214164845,198975943285110053,199643488563584807,200312646429253049,200983012100335454,201655385247526773,202328238711631128,203001570180938333,203676422910295082,204352856524941068,205028954831230186,205706601245752902,206385872839074102,207066602176989017,207746743398465068,208429528322450893,209113230167012795,209798173847686105,210484108079377339,211169315361937454,211857425550934197,212545301100830889,213236392651825107,213927062301079545,214618939485049068,215311356036294491,216006735471600356,216702596645396522,217399736884949086,218097169142752450,218795925918351095,219496291942274442,220197660127305370,220900540670103976,221604856290275104,222308748399966734,223014042944535702,223720428962088055,224426947552784569,225135528480843520,225843953921645630,226554651633770818,227267015801722094,227980265975676469,228695219032444401,229410556751625532,230126029069990273,230843054420611433,231561608679746012,232281665584253013,233003329928526425,233724537513342162,234447763437688694,235172243277502645,235896607411156235,236622717264700047,237349520963398318,238078199166180157,238807094424437274,239537799651359344,240270294936299076,241003465220194338,241736824412103463,242470600379438273,243206783619268782,243943463793646107,244681556980496312,245420652315372640,246160896276276670,246901884585370992,247645259602284753,248389683112579275,249133190646753762,249877601876373995,250623905206257750,251372299190595297,252121556384700067,252871665190343161,253622417736608460,254374049477890544,255128353964383794,255882304767183952,256637359129349901,257395872768586553,258153718597991740,258912371480900161,259673091127790204,260433246589528206,261194714801452482,261958081942238179,262722730224123338,263485856927023060,264253037782673794,265019975733161003,265788493393380411,266558620253543108,267328430264149998,268101481547363771,268873560287794055,269647849971630545,270423013757956709,271199310482012491,271976507665615567,272755003893137338,273535436054774646,274317139418050548,275097374527616012,275880069354999011,276664594704476429,277449621117053974,278235892917724252,279022573983459127,279812553730209100,280601576684846224,281390928423551877,282182842498076504,282975567351906205,283769032314818624,284563841708241444,285359564691764648,286156705825111204,286955864893414343,287755443382785029,288555202924772777,289356687936759018,290158855085376390,290962707454606991,291767060082602064,292572220311299254,293379336778371495,294187931977264504,294997580296288449,295806197646276547,296618014925158948,297428718132692575,298241840768203703,299056701194298323,299871483364009240,300686363205889028,301504171643287093,302323164267723087,303142401890925394,303961051556138574,304784538851229544,305608247988592723,306433073057733634,307258057473587640,308084152180970283,308912882050623862,309741717882064134,310571558386270716,311400746553528467,312231676343200842,313065496541724776,313900277876907720,314735368290637245,315570278915699957,316406891944176981,317244856921159138,318083797343442850,318923731457506466,319764859367899058,320606865491237047,321452035364656682,322297857760469865,323143851712468779,323991091826180775,324839167647814961,325688958663444864,326537951494675347,327388455422482465,328240607613760018,329093949801098506,329948908472022656,330803541803731051,331660251907259412,332517763056722699,333376021941021576,334235728970611210,335096261028614201,335958827496973571,336821736191268561,337685637333016458,338552182636368945,339418002011206931,340285226113947254,341153740131094826,342023014743570233,342892007180143700,343762854073554101,344635075124857675,345509046167865759,346383446125370419,347261090058488747,348137208468985574,349015784003804677,349896005016477532,350775754036165138,351656416678686184,352538358739519128,353422747587590093,354307666537970320,355191929968512122,356077598591717078,356964487317849255,357853723964160014,358743553936461396,359636051826716204,360527084463668437,361422121410903586,362317110116669464,363211307364886678,364108912336119367,365005975761239852,365904543712019919,366802889615356490,367704415821345968,368605371774958149,369507788994935567,370412807102643723,371317948454106477,372223502829519322,373129537497192057,374037448446222616,374947691326996962,375857568116004850,376768695304449636,377681177844429274,378594543943092085,379509522162110369,380425869670826826,381343692551305408,382261886679669913,383180624482875098,384099637887468207,385020333466232030,385942489065919116,386865708078654104,387790420263432341,388715762238397390,389641877104203720,390570730725202080,391499465083663402,392431115398948446,393362738483748043,394295334814665738,395230362745279130,396162417450701398,397097889789649417,398033511801952002,398971614967704191,399909713352397491,400847790591607459,401787836909180343,402729207108444244,403670707103439878,404615002580297573,405560360124066976,406506150891052617,407453069311034458,408404061632230764,409353265601403624,410303681936770744,411255048742042876,412208100823962134,413160819322419314,414116010332560022,415070252669457608,416027483398881099,416986178197590999,417944751360231077,418903847235591381,419865156321677190,420826828938302442,421791059651583607,422757483258810143,423723371245104282,424689280328267207,425656131423910825,426625381373587541,427593594764387918,428563023038187298,429536017428860270,430509933163735788,431483109736970902,432459791723073382,433437693558683915,434415822065180752,435392988381870282,436372424223640101,437354192121862477,438336695051823641,439320289938170103,440303125328156729,441288323542794380,442275764843964446,443262638339322735,444249536424274469,445237707725051313,446227329777320757,447219076492000678,448211522040791372,449207529536729122,450200902369004410,451195602682517922,452192955038773187,453190905753545191,454188047099980131,455187912329484245,456187492338256656,457189732682611662,458193517218509024,459197383719838090,460201454210706792,461206862751768436,462213875212614495,463222257880688071,464231209702294799,465241801240068562,466256158281531596,467269855419056305,468282176489204657,469297520138658642,470313903362280398,471331127307860565,472349380286542359,473369107094436378,474390398971207154,475411561552802398,476432607272041891,477455381156305757,478480891244239645,479507116153426173,480535530035390728,481562925475000592,482590367831839375,483620216438493252,484650720495084997,485683937173319440,486717454783501904,487750909093664676,488786900564253129,489821571511334918,490859590163437709,491900328090175243,492939285361099003,493980240470015602,495019443378198105,496064952734900197,497107907956781535,498150360254754104,499198106484334837,500244833125442678,501292747562487143,502343032515144753,503393827995557040,504447418466870322,505499791101190150,506554045642407584,507609198380309810,508663795051761493,509719512938381692,510778143765287545,511838374418055573,512896960667258753,513958251150968666,515020375327383930,516083987237445493,517147824346048385,518214525179075598,519283466812952952,520350806321523197,521418301275163811,522486759986576892,523557002916953192,524627129232550339,525700460949671292,526774546341229228,527849811028243714,528925141442346284,530003465642014980,531080355828689214,532161772728699382,533241682466762064,534321908452054939,535403558006716787,536487101000777575,537572404408189517,538657226827303294,539743575640848963,540831393988822620,541920333555624019,543009825870107009,544099786176162989,545193433058750186,546286646646268632,547383588297320264,548477390831149094,549575517339782773,550671553012742456,551769163824910852,552869910450502239,553969284488776738,555070430089767718,556173591429792024,557277839235528649,558382537263056964,559489356551457208,560596125187599449,561704301442537660,562814111845026849,563925271202513678,565036374837024316,566147281431880999,567261817069073969,568376612715641980,569490047175776721,570607157098174525,571724717987983239,572840944428163512,573961259384457261,575083655296819260,576207823696943695,577332340284405368,578457436127908825,579582680996208145,580709256375193563,581835370045993085,582961703133600465,584090651710270748,585221376733502077,586353229948760302,587485711557813172,588617669102650384,589754401418649753,590890455968005614,592027248134885028,593165977914626291,594305317823916950,595443497444503440,596586253785728530,597728336491354233,598873996757662489,600017789144835905,601162760730292105,602310844260506342,603456649281107977,604605425003348183,605755827446433828,606907246018232447,608060555547067310,609213468471490175,610366250511617306,611520876748188974,612677969884032627,613835855586724773,614992579771591603,616153111855458638,617315043401239601,618476050430444525,619639443561211417,620803653593816127,621967865713602853,623133579860626747,624300098230333561,625468711304635386,626636908373216338,627807248018227564,628980037925997696,630152718812293454,631324178492853855,632499671837691205,633674692520790775,634852531454428478,636028605127122114,637206684948489645,638389526685451262,639570806919655280,640751897098908325,641936280504908823,643119628744237615,644302691875745113,645488882578129624,646676556845533240,647862643963636982,649053270639849593,650242023098526421,651433400927973436,652626995390900563,653820563526423402,655015862492091642,656213591196162593,657408602866333245,658606709361118444,659804690934727148,661005459940498987,662207172968175006,663406926641480498,664610009091743085,665813873290601990,667019711576320894,668223902279518601,669433044168080963,670642695704252425,671851474312576074,673061470444582418,674270196142377405,675484302683369065,676698551040846022,677914650828130178,679131305231909181,680350396755660372,681568911017190913,682786463373543252,684009195049260402,685229291499285597,686448945091734890,687673387190686873,688899670790118350,690123321044805545,691349030043155916,692577455930019930,693805299209375326,695034752064660052,696266225050219998,697496630254928351,698728120243533435,699964666610929619,701200145659907311,702434076139250341,703672615989429893,704912682594282467,706153865285963445,707392545564639003,708634979038473425,709878338117957643,711123246313299241,712368717059708584,713613792563619083,714861586987055749,716109404003015796,717358524903939819,718610336948214469,719862016870902785,721114236944605359,722368567449185530,723621838635222517,724877637211028483,726135660983010574,727393003731742657,728649741236041550,729909757066356460,731170971471594351,732435271526043012,733697567440986931,734963973600456810,736230438141357283,737495087414783477,738763114624816767,740029076071836371,741296998689364768,742568971434761592,743840099404887483,745115068184634501,746386087631011700,747660502450618356,748936586206921293,750213300645744678,751492166485977868,752770789509198410,754050951069892486,755330157969062427,756612204024171120,757895247875332469,759177302754898226,760464419716706715,761748811617084326,763036073635651219,764322605519311326,765612253647321333,766903878109998997,768194769255298113,769487498041741722,770781013038364031,772075581753459376,773370527859814891,774668107546434785,775967055959771315,777263219931628004,778564978676384452,779863782632912871,781167516176488702,782470421422098278,783775957514849233,785083299506235840,786390050017257831,787695500657535730,789002102098348280,790313259926624715,791621295510521088,792933645798656782,794248324744431806,795558782822900470,796874462104144231,798189073415967184,799507924344977659,800827081111974574,802145337048088674,803465107000021532,804787039774544755,806107013450574282,807432533189863648,808754598446556964,810081734076330804,811408811803593404,812738262080357593,814071180604641758,815399501477370447,816729819086695334,818062002011808623,819394671819309306,820729004452747925,822063737252171862,823397834816913161,824735968259451448,826072168720985866,827411316428738275,828751471923014929,830092471918637101,831432059858575888,832775484723546404,834121703897917816,835468797080559435,836816891838401260,838164920456112547,839512721710099808,840863237981784125,842214169594312310,843566503201499385,844921526781079813,846273694653415627,847628392792949764,848984756655793636,850341746714293673,851704518221259759,853066256677235499,854428192998263292,855787808552527338,857153341971918829,858515585891419662,859879453710278067,861244337891592301,862613090419626867,863979598823594833,865349424943945761,866720645497049627,868090347523901704,869463181043286278,870838473897212370,872214691192566628,873589376170360924,874965604064258696,876342206347495486,877720489602687524,879099694757620146,880478418874115255,881861353892090056,883245373589329621,884627800033268659,886009734219343173,887397239791537153,888784345954478160,890171858843375055,891558988825015180,892951929430609957,894344574392827802,895738510057692216,897132598807259754,898527004253696810,899924419306443728,901319294897332635,902717453085001211,904115355878955549,905515706278305683,906915513755335500,908316504402095977,909719919801639672,911122116662710142,912525673875983388,913932711250095842,915338322323382727,916744474122670061,918155599956186187,919566498638339135,920977471832576707,922390521561736305,923804187250812158,925217587573063844,926632982897564651,928047124587856811,929465944697183125,930884264172515550,932304170545304900,933721725886788375,935143892175867340,936567905191149042,937989146987662919,939412986274202200,940839819639673886,942268211424453000,943693638899721303,945122851927594889,946554767459827784,947983231262611514,949416307975035284,950850535968935653,952287057291355451,953720081249093367,955157624707214469,956596560563758111,958035277401375537,959476766449355861,960920965578342395,962364670395771291,963807558492371828,965252786176561124,966698297610364652,968146706477503682,969593502985573770,971039931561814387,972488938440566863,973937536608714324,975390303192641672,976842942699339942,978298206425765997,979753109865954983,981209178659455130,982666215461907554,984124245959931901,985587776435275044,987046479383752560,988506869143621360,989969296181234269,991432531790082359,992897647350877742,994362875117494255,995828677030656774,997297562377182657,998765089685382801,1000234120939338515,1001705713712648044,1003176947665397415,1004644929703588776,1006121487817062972,1007596403554115712,1009073573264039024,1010553727083713571,1012030374112998426,1013510145662757015,1014988223343232588,1016469161075239551,1017952531101669498,1019431845394198142,1020914578965334375,1022400856348096153,1023889975329701785,1025377150236396132,1026862594045000604,1028352214753757686,1029844823454405237,1031336666613821083,1032831757058603840,1034324558644169349,1035819641758024510,1037315273436012585,1038816198843310538,1040312804030564419,1041812543270458473,1043314215474042277,1044812643680403333,1046311016209356443,1047816222468303407,1049320475776371201,1050826516675561759,1052333265595098873,1053842757547223145,1055350047728031069,1056859548834111051,1058368244836044026,1059879864807929463,1061390758190506081,1062906498818378941,1064417319372886917,1065933347256834857,1067451839623526151,1068968940482412720,1070487481978920406,1072004591676965958,1073526627477348371,1075052333943930740,1076578201685671808,1078101823574723545,1079627930566384248,1081152913902831367,1082681353575495036,1084208057274770395,1085736333575735992,1087268244613658478,1088801800953125710,1090331716631679965,1091864485243655638,1093398453723986147,1094937068994865077,1096473465674213512,1098010531922098797,1099550941174553083,1101088968923527402,1102631284419675343,1104176913629298658,1105720106635140801,1107262596778570078,1108806937177428886,1110355500431029177,1111902844932948139,1113452928276010942,1115004256079230967,1116553438576895358,1118104503421838894,1119657916093519243,1121214680478190171,1122768148603489825,1124328568816040660,1125886329893632314,1127443441673951630,1129003416295429771,1130563920080396681,1132124180800761911,1133688072740136516,1135250060782268303,1136816620626555729,1138381074945182999,1139946430843802615,1141513364141272400,1143079961719328711,1144652844836972556,1146225071918331190,1147796989187685736,1149369794878862918,1150940694074142119,1152515109609861732,1154090205285022286,1155667724751554923,1157245773846859538,1158825512244763461,1160404501920160618,1161984240855038476,1163567896328049664,1165149290750399848,1166734028866620658,1168317299112456669,1169904708482317956,1171492189721453676,1173078528169549403,1174668709995170988,1176261524164759509,1177853019010160207,1179443829216071376,1181036968862874843,1182632658676094228,1184229246904635845,1185826842022779537,1187423739073398781,1189025824818089606,1190628105333563226,1192229117468781294,1193830662376602252,1195430721978336935,1197034926035361556,1198639618069922501,1200245541997053002,1201853435880533878,1203462247773685511,1205069674384732158,1206683212984153282,1208296301434200328,1209911165896360316,1211526442134638658,1213143113520730872,1214759749200167655,1216375846772830609,1217991492233980024,1219609781187704611,1221232373179948853,1222853194639748029,1224470028197692201,1226091912034950641,1227717139417479603,1229342640610960797,1230973396114697411,1232600964336312767,1234230209769312291,1235863112265342994,1237493854914667815,1239129436102663220,1240759774257696342,1242393415576124525,1244028848268150125,1245664719268338724,1247301816455652560,1248940340413086338,1250581499746622884,1252221121168243244,1253859781673712764,1255504132248213759,1257143666368838530,1258789112848783437,1260434342642046084,1262081308129594170,1263731478746816705,1265378739308553435,1267029522246884132,1268680286436719838,1270333614999800043,1271985232272398838,1273636812088689314,1275293448968648308,1276948919316433161,1278605035937323622,1280260705748480774,1281920310192713650,1283579527101792715,1285242441049678984,1286904338358841421,1288569391869402924,1290234463552659578,1291894042321384964,1293559674833689754,1295227528699414930,1296891872895980607,1298562540475642134,1300230172023646437,1301902064726673440,1303574698967250986,1305249033860134137,1306927508452866609,1308603590673345627,1310279871165993511,1311957546852986174,1313635327769847459,1315313808540487430,1316997021472704764,1318677268972386545,1320361027091439639,1322046082916570829,1323730149715448313,1325418017062581247,1327101998538011052,1328792256961881707,1330482183394474556,1332171191600264971,1333860302497061747,1335553254643519527,1337247251526114192,1338945008415458008,1340639370830100412,1342337303287949848,1344034270175548023,1345734206372676762,1347434079634632489,1349132982171770195,1350837020299604260,1352538728697041449,1354245197323534948,1355952618860021944,1357658573996876462,1359366691325092335,1361077292180202726,1362784919476137682,1364494235461878848,1366204523041403062,1367917842509291406,1369632080726350535,1371346425239323533,1373062530648265710,1374782213362680336,1376502572692887110,1378223066931122875,1379943789591992329,1381665093131144355,1383388309753828675,1385107952226492290,1386832303643345769,1388559836753876609,1390285367856079999,1392011846161169588,1393737696051889496,1395468819669892130,1397197799588621797,1398928340488422661,1400661754994734094,1402398550978263598,1404137070438801943,1405871181078509702,1407605034561573432,1409343277935733712,1411081945401154597,1412823208675695355,1414563609326372316,1416305431496932524,1418049128812405032,1419792212670451067,1421539815082649612,1423286652712443651,1425033288922274383,1426779808641716787,1428534667517733009,1430284646750306112,1432037711224642182,1433789515151380383,1435543734762318279,1437300147743476306,1439060500549692478,1440816263488059042,1442574429411053305,1444332672526677239,1446092059555975487,1447850734828678776,1449612835606094429,1451377279612651415,1453139738635122360,1454906248081720572,1456671389206801940,1458438689256500848,1460206656878449021,1461977836184229100,1463751541907267076,1465524971589578296,1467294775312665070,1469068870153353329,1470843859001431283,1472617390351734230,1474394480953107149,1476171386063961446,1477951156400279699,1479728294784245035,1481509640382587002,1483287892849409794,1485071283291563331,1486859017738039611,1488642905636299516,1490426387519513997,1492213475727091802,1494001642843459627,1495792914491227542,1497580983360794917,1499369607035950446,1501163480684222077,1502956199130981837,1504753035847056482,1506549779442325540,1508348521557116506,1510149107726574163,1511948654947140316,1513749528496705399,1515551102304308504,1517350917949273674,1519154617649970493,1520959379538843390,1522765912810992999,1524569128982549415,1526377704622078360,1528185923504481829,1529993221436093300,1531806201136450550,1533619996524188124,1535434399684506599,1537248333233793875,1539062682154448311,1540875016125849146,1542691902835967086,1544513213808373773,1546330778417702097,1548148588648363111,1549967385239714072,1551789680442278884,1553609189481359612,1555434074088045336,1557260695577240489,1559086050910092891,1560914186609526871,1562741037000819092,1564572282597689648,1566403729037613187,1568237650523838589,1570068465352737785,1571899945765881986,1573734045017530299,1575569675166121680,1577400481977332994,1579240675986073156,1581080411115535437,1582919837368425255,1584761232949542353,1586601382538972293,1588447055985464925,1590290108215872866,1592134953502299660,1593981145129487946,1595823964807711031,1597672336661951198,1599518836588578762,1601367053946671660,1603223253257205684,1605072165395457336,1606921627182876936,1608776156709739239,1610632984079667552,1612491254433741868,1614346644766832118,1616205982487186976,1618066695111524227,1619925881764185144,1621786254065057048,1623650674809541845,1625516386422629483,1627379107943968506,1629244577776965845,1631111840242214570,1632979957104361113,1634850825805521202,1636724311101361819,1638592806715870393,1640467609233905942,1642340361474049320,1644215072497891235,1646085379142150539,1647960586795840265,1649841000251589354,1651720876117259529,1653599240578582283,1655480822486383774,1657363360247528035,1659242780753003775,1661124343181755875,1663009152450039619,1664895175962526153,1666780979849409689,1668668731473584414,1670558068562394186,1672447088778748501,1674335315023362918,1676227410916844484,1678118694671288256,1680010914632042440,1681905127599449500,1683800527520475609,1685694119881210514,1687592972566003063,1689494213305350807,1691397705226280304,1693298348690591406,1695202043811688159,1697104139872644201,1699009759374873260,1700914534948557177,1702820559683315482,1704728707309976185,1706637614734962972,1708546521768028726,1710453599578417108,1712363351614743849,1714276549703208561,1716187011544020238,1718101745557443068,1720016614795454049,1721933735598579784,1723854820132632540,1725773930722712231,1727693993110233726,1729615789373476960,1731538924730867632,1733460959109007061,1735384216208897297,1737310081875122111,1739234656973309183,1741164577779378807,1743093816675094972,1745023998226041176,1746955819576100862,1748887530025587664,1750819826925009595,1752753968449323283,1754686773921902147,1756621964485331031,1758559079837931463,1760495146987934498,1762435653195086434,1764373297738042007,1766313792239503686,1768256036598345709,1770195446048063287,1772139979965152228,1774082549054377874,1776027981562340911,1777975549614508613,1779926101461421019,1781876655549146067,1783825576106042404,1785778001512186421,1787731115921414453,1789683146647086516,1791638935844957233,1793590663456586247,1795546807045789392,1797505216915521248,1799466791960137409,1801424554976007552,1803385430088263930,1805347296505786219,1807310307011831226,1809273482194818418,1811240071336574214,1813206824315318055,1815177058452629029,1817146787549137510,1819116370980138096,1821083415511937142,1823055443320454309,1825025921636994758,1826998249885678387,1828972147525039683,1830947334442012621,1832923757028395827,1834900916380093284,1836879510835851031,1838858578451610336,1840839026330971833,1842821509632363006,1844805902145433317,1846790303624737209,1848771034560558950,1850755612744011584,1852746265858504549,1854735156354433979,1856719819289342562,1858708545538548329,1860702635974001142,1862694537973722202,1864686121864052268,1866677935354491152,1868671047617849767,1870667419600398441,1872663891757280725,1874656859572708446,1876655951197354054,1878660803518734657,1880657629343393645,1882656286928556352,1884660417255726928,1886661692205349179,1888670800888417249,1890682041366821582,1892687326149589606,1894696279983261518,1896705337114640285,1898720614215076856,1900734157763859125,1902747831142025392,1904762696623136696,1906775563583296958,1908793876085569353,1910809447127461282,1912834174369180302,1914854016031285423,1916873677766680761,1918896014759840244,1920917520353316334,1922945288204818333,1924968664409804606,1926993938719904350,1929018237099603478,1931044898494238755,1933073822036671248,1935105120021738173,1937136231735356629,1939168451968924955,1941202852114623484,1943232432408497194,1945264425833162452,1947300862361414739,1949335741710250431,1951373824166694229,1953412545687194439,1955449181127034148,1957486687505969578,1959531592100560589,1961574434680528232,1963619295307158016,1965667461555220268,1967714932253491132,1969760587318268287,1971808044575984882,1973857051915982750,1975912533670748818,1977963605076501340,1980013567270032209,1982065975569423636,1984125605976686717,1986180105029252183,1988236873554315056,1990290145389072298,1992349165939424779,1994410571203453065,1996471238626017654,1998531687091768903,2000593470179890060,2002657080452032391,2004718799507751570,2006788639230951694,2008852607041741995,2010919847160049950,2012987947042232211,2015058608412601581,2017130987343719601,2019201826204495311,2021279555133874074,2023353283562084189,2025429196522731417,2027501769883496269,2029577071275419913,2031654395252426919,2033735140236806375,2035817604252982399,2037900984592677469,2039981710655960928,2042064069368884458,2044154137547527213,2046237559214705265,2048324723975470526,2050413053202215967,2052501779236192134,2054592236923702188,2056684272422543911,2058776290147165065,2060871416430004325,2062968882877440039,2065060136999233959,2067156254289085973,2069250740382723941,2071347692416231544,2073449592071934819,2075552387638297014,2077657450060078583,2079760779022155658,2081862864961756372,2083969085714720259,2086074002551299333,2088183939430481829,2090290836550728211,2092402176868168005,2094514052329245516,2096626763623632565,2098740728294545685,2100851418402169548,2102963281605084504,2105077485358854279,2107194800049044864,2109312004681886670,2111431280927212419,2113548213575394326,2115669811715394270,2117785696506240205,2119907858786420862,2122033481754598024,2124158502584792957,2126282585976836515,2128407952157915137,2130535353290535202,2132665496123597058,2134793777465307693,2136929359785784794,2139058744319532220,2141189773864978181,2143322321073810260,2145458037599413579,2147590830811570316,2149725958619406200,2151868713397576009,2154006829317610034,2156143156103547569,2158282429209005889,2160426750970406383,2162569803231385946,2164711583417013718,2166859523571479240,2169005696809774171,2171154736023986682,2173300649201224773,2175447776994947949,2177602274533992984,2179749898737928209,2181900984868462320,2184051958310268930,2186207894086780401,2188364370459719551,2190522966987353517,2192679839076385818,2194839347482461769,2196998878323076915,2199157495619586254,2201321357718383971,2203482971410698097,2205647752445478822,2207814527893083686,2209976286333240314,2212141324384390282,2214310521399831036,2216480355566767723,2218652355513936408,2220822432581729236,2222994255677416578,2225171107472122712,2227348666318534284,2229523565555675880,2231699229645937070,2233871998391001423,2236051016857013385,2238228221044632612,2240408397905585319,2242588031880796170,2244773053655752815,2246955802204412620,2249133477976797809,2251318578546800056,2253507282829129615,2255696619492498465,2257886942699722643,2260075224272626619,2262269586301173626,2264458804175542282,2266651097439525481,2268844556532098214,2271035541055512615,2273232626868205102,2275427164430112804,2277626969410748085,2279821406566206329,2282024883384272078,2284230248346814862,2286429566727678511,2288631004945373908,2290833405300330009,2293038911279926751,2295245655073529798,2297453057101792011,2299660618204416153,2301868998250295313,2304076976055900845,2306289533052163590,2308501524470702799};
LL segment_sieve(LL a,LL b){
LL t=sqrt(b),n=b-a+1;
for(int i=2;i<=t;i++) is_prime1[i]=1;
for(int i=0;i<n;i++) is_prime2[i]=1;
for(int i=2;i<=t;i++){
if(is_prime1[i]){
for(int j=2*i;j<=t;j+=i) is_prime1[j]=0;
for(LL j=max((LL)2,(a+i-1)/i)*i;j<=b;j+=i){
is_prime2[j-a]=0;
}
}
}
LL s=0;
for(LL i=0;i<n;i++){
if(is_prime2[i] && a+i>2) s+=a+i;
}
return s;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld %lld",&n,&mod);
LL ans;
if(n&1){
ans=(n-1)/2%mod*((n+4)%mod)%mod;
}
else{
ans=(n+4)/2%mod*((n-1)%mod)%mod;
}
n++;
int m=n/len;
if(m) ans=(ans+sum[m-1]%mod)%mod;
ans=(ans+segment_sieve(1ll*m*len+1,n))%mod;
printf("%lld
",ans);
}
}