2020杭电多校联合训练(第一场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第一场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKL
场上
zyj
wrf
lmj

题目

C.Cookies

lmj (赛后)

题意

设f(x)为$\sum_{i=1}^xdivmed(i)$,divmed(i)代表i的因子中的中位数,给定n个数m次操作,每次操作去掉标号为P[i]倍数的所有数并重新编号,求最后第k个数的答案。

题解

先不考虑答案,仅求出第k个数,那么可以使用二分答案来完成,二分答案看他在最终序列中的位置。对于答案,可以发现中位数就是小于等于$\sqrt{x}$的最大的因子,那么可以考虑筛的时候枚举每个因子的平方,将那个位置的答案改成这个因子,考虑分块打表,表长为2500000(没开O2打了我40分钟。。。),然后就可以得到块内的前缀和,然后再前缀和一下就是前x个块的前缀和,块内部分暴力筛完成即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
ll p[N];
int ans[2500005];
ll n,m,k;
const ll pre[4005]={0LL,876804130LL,1563212084LL,2002063203LL,2354317781LL,2656733732LL,2925711704LL,3170453898LL,3396438608LL,3607003882LL,3805141120LL,3992850026LL,4171496143LL,4342381148LL,4506248314LL,4663920548LL,4816343829LL,4963323315LL,5106068055LL,5244637694LL,5379239197LL,5510576882LL,5638406672LL,5763277881LL,5885273702LL,6004611649LL,6121491911LL,6236207560LL,6348621224LL,6458737714LL,6567208205LL,6673519997LL,6778204006LL,6881218772LL,6982516261LL,7082317814LL,7180625602LL,7277588377LL,7372946342LL,7467494111LL,7560199220LL,7652003830LL,7742655785LL,7832126306LL,7920669641LL,8007834664LL,8094421101LL,8179564557LL,8264105204LL,8347670862LL,8430063727LL,8512607591LL,8592814367LL,8673268528LL,8752693851LL,8831052973LL,8909346200LL,8986432928LL,9062139581LL,9138686315LL,9213456643LL,9287955306LL,9361822485LL,9434993654LL,9507766127LL,9579922414LL,9650840476LL,9722096732LL,9792157823LL,9862088957LL,9931335255LL,9999822464LL,10068888693LL,10136703575LL,10202919089LL,10271306698LL,10336034232LL,10402976823LL,10468266692LL,10533777507LL,10597973483LL,10662291485LL,10725848841LL,10789479554LL,10852326481LL,10915329341LL,10977449357LL,11039240482LL,11100750009LL,11162211406LL,11222963707LL,11283689287LL,11343155094LL,11403034701LL,11462439946LL,11521637500LL,11580021523LL,11639525364LL,11697108953LL,11755025796LL,11812054069LL,11869984099LL,11926764019LL,11984012354LL,12039309964LL,12095872616LL,12151449134LL,12207504976LL,12262438889LL,12318022364LL,12372214180LL,12426738793LL,12481607845LL,12534981617LL,12588495594LL,12642140251LL,12695627735LL,12748804273LL,12801426803LL,12853967764LL,12906904768LL,12958401044LL,13010399730LL,13062369195LL,13112953880LL,13164978712LL,13216035823LL,13267163122LL,13317504058LL,13367618467LL,13417354827LL,13468217414LL,13518786502LL,13567121264LL,13617318586LL,13665894015LL,13715376757LL,13764105477LL,13812896411LL,13860763742LL,13910515319LL,13958249955LL,14005439269LL,14054325127LL,14100931210LL,14147539972LL,14197979581LL,14242601150LL,14289597007LL,14337520608LL,14383449267LL,14430039817LL,14476485577LL,14522991584LL,14568458231LL,14614795255LL,14659517469LL,14706141637LL,14750126879LL,14797080888LL,14841887237LL,14886334659LL,14931103983LL,14975142940LL,15021324552LL,15064103306LL,15110281980LL,15152098347LL,15197342376LL,15241013743LL,15284700840LL,15329274722LL,15370786786LL,15414962960LL,15458593539LL,15501261899LL,15542719005LL,15587220816LL,15629458010LL,15672940561LL,15714102155LL,15756967471LL,15799110472LL,15841048275LL,15883225551LL,15924394099LL,15966678852LL,16008827117LL,16049378701LL,16091379502LL,16131818876LL,16173654505LL,16214723437LL,16255570734LL,16296890703LL,16337300894LL,16377384526LL,16418238412LL,16458588808LL,16499611286LL,16539040277LL,16579621877LL,16618868558LL,16659513775LL,16698367345LL,16739836556LL,16777551664LL,16818523903LL,16856171740LL,16896655941LL,16935450348LL,16973926760LL,17014863925LL,17051920773LL,17092384518LL,17129753719LL,17168290745LL,17208303275LL,17245980443LL,17284773320LL,17320932388LL,17361343532LL,17398646751LL,17436965464LL,17474181297LL,17512963048LL,17550433580LL,17587120120LL,17625299153LL,17663103422LL,17701555379LL,17736819119LL,17774535099LL,17812743497LL,17847494120LL,17885631466LL,17923526442LL,17959117300LL,17996933288LL,18033429293LL,18069162914LL,18106744186LL,18142307432LL,18179131590LL,18215555985LL,18250085650LL,18288755945LL,18323655912LL,18358385950LL,18397032412LL,18431596024LL,18465914273LL,18502820743LL,18538133557LL,18574490067LL,18608755338LL,18645332793LL,18680523358LL,18714645230LL,18749891803LL,18785427920LL,18819893925LL,18855125367LL,18891909782LL,18926068981LL,18959653489LL,18993376107LL,19028925753LL,19064370720LL,19099473483LL,19131660921LL,19166008548LL,19201570859LL,19236959169LL,19269896699LL,19303172154LL,19338384692LL,19370492076LL,19407043575LL,19439538914LL,19473431659LL,19507026966LL,19540294861LL,19575055800LL,19607580531LL,19641703994LL,19675088394LL,19708176270LL,19740924676LL,19774026186LL,19808666377LL,19842408610LL,19874663879LL,19906447074LL,19940041276LL,19972174554LL,20005465227LL,20040137295LL,20071395347LL,20103304032LL,20136827907LL,20169403231LL,20202168502LL,20232047232LL,20268619392LL,20298403141LL,20330431037LL,20363017913LL,20394211228LL,20427939964LL,20457925374LL,20493935294LL,20522793432LL,20555425974LL,20586816285LL,20618911006LL,20650570701LL,20682593322LL,20713708152LL,20746648865LL,20775879284LL,20809502533LL,20839364151LL,20870923968LL,20902958983LL,20934489584LL,20964709028LL,20997484942LL,21028071818LL,21058446668LL,21088472986LL,21122623551LL,21150996079LL,21183130066LL,21212387768LL,21244529323LL,21276150752LL,21303977911LL,21336279988LL,21366910986LL,21397391902LL,21430572980LL,21456663577LL,21489070769LL,21519737838LL,21549267191LL,21579950890LL,21609840501LL,21642490194LL,21668573324LL,21700017704LL,21732198579LL,21759689907LL,21792387046LL,21818552197LL,21852590357LL,21879270994LL,21911459419LL,21939671713LL,21969723732LL,21999797249LL,22028669322LL,22059384243LL,22087213300LL,22117434195LL,22147016089LL,22176092793LL,22206438999LL,22234685237LL,22264105432LL,22293710400LL,22322855915LL,22351215681LL,22382636284LL,22411453494LL,22439430853LL,22467533229LL,22497418963LL,22526590617LL,22556399019LL,22583529510LL,22612789761LL,22643316737LL,22670053877LL,22698780712LL,22727569582LL,22758413414LL,22783540335LL,22814725504LL,22840178391LL,22873248800LL,22899340125LL,22928136916LL,22953543724LL,22985919157LL,23012228753LL,23040379259LL,23070217897LL,23097434233LL,23126446079LL,23153449338LL,23180090453LL,23210312516LL,23237358978LL,23266943874LL,23293948361LL,23321546433LL,23349116448LL,23377177364LL,23405472690LL,23433662726LL,23459474430LL,23487940568LL,23515271066LL,23545102968LL,23570434254LL,23598572447LL,23625525791LL,23655594812LL,23682428660LL,23707311519LL,23735279232LL,23763991315LL,23790511341LL,23817547772LL,23845194790LL,23872749450LL,23900330625LL,23926355034LL,23954227133LL,23981637439LL,24007970423LL,24033099999LL,24063508976LL,24088356288LL,24115621450LL,24144481135LL,24168490030LL,24197007268LL,24223067229LL,24249528767LL,24278046976LL,24302620066LL,24330270407LL,24358313609LL,24382043079LL,24410191188LL,24437304928LL,24460845608LL,24489674148LL,24517248973LL,24544261037LL,24567752208LL,24594197332LL,24623039101LL,24647786448LL,24674283142LL,24699885203LL,24726908162LL,24754528754LL,24777857418LL,24806020082LL,24829921381LL,24859230378LL,24881546849LL,24909160385LL,24936861221LL,24961018703LL,24987138565LL,25012536193LL,25039573699LL,25065655984LL,25090859156LL,25116956494LL,25141113236LL,25167200513LL,25194925559LL,25219584303LL,25246030747LL,25269461711LL,25296649666LL,25322816536LL,25346500113LL,25372766904LL,25399771261LL,25422193505LL,25450232342LL,25475682720LL,25500098387LL,25524796651LL,25552291090LL,25573965879LL,25602609529LL,25626335596LL,25653188707LL,25676577175LL,25702153450LL,25727671818LL,25753950870LL,25776447864LL,25803629010LL,25825876236LL,25852807509LL,25877889248LL,25903963287LL,25926657509LL,25952004432LL,25979271239LL,26002468852LL,26026582654LL,26052337042LL,26075863322LL,26103853116LL,26123593382LL,26152704203LL,26174412260LL,26200445065LL,26226338287LL,26248172131LL,26274106632LL,26299100989LL,26322791027LL,26347553468LL,26372000325LL,26396630980LL,26423412461LL,26443943609LL,26469081633LL,26493779604LL,26520312195LL,26542368288LL,26567390292LL,26591148589LL,26615492376LL,26640383006LL,26663807647LL,26688313210LL,26713806890LL,26735483901LL,26761720757LL,26783725134LL,26808301307LL,26833863251LL,26857591854LL,26880311449LL,26906895236LL,26930149817LL,26950946087LL,26977259036LL,26998560392LL,27025714735LL,27049885920LL,27069510308LL,27096453872LL,27119235417LL,27141728971LL,27168543157LL,27192319076LL,27213512828LL,27239304959LL,27262401969LL,27286541811LL,27307921141LL,27334296367LL,27354042110LL,27378620886LL,27404715197LL,27425212865LL,27452988845LL,27474162407LL,27496920095LL,27520671916LL,27542454807LL,27568867996LL,27591048820LL,27613562770LL,27637802449LL,27660816204LL,27682479758LL,27709778608LL,27729824013LL,27753228187LL,27778283343LL,27798413915LL,27822370967LL,27847780316LL,27868525590LL,27892846216LL,27916505000LL,27937943532LL,27960598880LL,27984371190LL,28007382693LL,28031372478LL,28053084507LL,28077511190LL,28100249538LL,28121111707LL,28144850624LL,28168110833LL,28191425439LL,28213498128LL,28236914697LL,28258933769LL,28283996229LL,28303228342LL,28325103826LL,28351662345LL,28370907208LL,28396548174LL,28418655320LL,28441089216LL,28460374760LL,28485629867LL,28509009781LL,28529294785LL,28554706895LL,28576659618LL,28596115797LL,28623249230LL,28641294246LL,28665341804LL,28690120518LL,28710907668LL,28730389978LL,28753769056LL,28777489356LL,28798795532LL,28824345104LL,28844811537LL,28865918937LL,28889047880LL,28910908001LL,28932190628LL,28955663267LL,28979224737LL,28997612630LL,29021790743LL,29043565874LL,29066194545LL,29091133154LL,29108623004LL,29133386356LL,29152393464LL,29175703300LL,29196997854LL,29222083463LL,29241220717LL,29262963568LL,29287189463LL,29309712783LL,29326913081LL,29351594343LL,29375673653LL,29393645784LL,29417112881LL,29440773212LL,29460124460LL,29482610224LL,29503266305LL,29525246499LL,29549437000LL,29569840901LL,29588605752LL,29614427377LL,29634497509LL,29656358324LL,29677972436LL,29699355990LL,29719557007LL,29741333413LL,29762832362LL,29787518050LL,29807097100LL,29826124116LL,29852827009LL,29870511883LL,29891479995LL,29914432989LL,29934104078LL,29956023742LL,29981978406LL,30001166432LL,30017856984LL,30042947862LL,30063537983LL,30082745579LL,30109550646LL,30127830696LL,30151016369LL,30170049341LL,30188383050LL,30212674335LL,30235416145LL,30254005360LL,30275693353LL,30300736441LL,30314434110LL,30338930475LL,30361638909LL,30384230419LL,30401308258LL,30422973535LL,30445945275LL,30466189745LL,30488343179LL,30505158453LL,30529861318LL,30550244286LL,30570210714LL,30592038376LL,30612710633LL,30634466757LL,30653749326LL,30675135565LL,30694428262LL,30717707615LL,30739347598LL,30758198787LL,30780286787LL,30801227412LL,30818325229LL,30842253480LL,30862562674LL,30882606224LL,30905951397LL,30921807336LL,30946258107LL,30966675713LL,30982755181LL,31009255924LL,31027723739LL,31047716589LL,31067153033LL,31092586596LL,31107411601LL,31134136798LL,31146898089LL,31173704104LL,31191121558LL,31213492850LL,31233454825LL,31252312750LL,31274387870LL,31291732677LL,31318961219LL,31332711560LL,31357141819LL,31375193672LL,31397687913LL,31419228862LL,31436242072LL,31455825041LL,31478976012LL,31495647531LL,31519501812LL,31539532020LL,31557208049LL,31580939853LL,31599197528LL,31618223362LL,31640934390LL,31658130716LL,31679214698LL,31699760382LL,31721935731LL,31736324154LL,31763834743LL,31780911682LL,31798637848LL,31819537498LL,31841082148LL,31862567660LL,31882289147LL,31899379987LL,31921769328LL,31943761880LL,31959372466LL,31979340103LL,32000794336LL,32022580785LL,32039330115LL,32059884772LL,32079465128LL,32105097652LL,32119114133LL,32138028430LL,32161603798LL,32178024243LL,32200388542LL,32219331269LL,32239568493LL,32258306192LL,32281330722LL,32296782196LL,32319153217LL,32337298900LL,32357023210LL,32378518768LL,32396636360LL,32418486036LL,32433648574LL,32456748873LL,32476746778LL,32497119715LL,32514691919LL,32533870704LL,32555626619LL,32574499716LL,32592253659LL,32615637268LL,32627904404LL,32654732610LL,32670475152LL,32692327229LL,32709815509LL,32731414409LL,32750081820LL,32766089242LL,32787951710LL,32809785657LL,32828328938LL,32845838610LL,32867034386LL,32884761928LL,32906124705LL,32923606732LL,32942948280LL,32965578522LL,32980494478LL,33003620003LL,33017387170LL,33038859989LL,33061069683LL,33080663519LL,33096626980LL,33119198843LL,33135750195LL,33158881100LL,33174477926LL,33191885645LL,33213249531LL,33229817878LL,33256594741LL,33269555643LL,33288034360LL,33309904159LL,33327817652LL,33347208484LL,33368072772LL,33385282812LL,33403187242LL,33424715702LL,33443838700LL,33461702851LL,33480467072LL,33497224216LL,33520647853LL,33536425600LL,33558029325LL,33576600980LL,33593724444LL,33615621188LL,33630790192LL,33650026089LL,33672036133LL,33688925400LL,33708056080LL,33726977790LL,33746296540LL,33763256436LL,33780977863LL,33806148321LL,33818525553LL,33839606667LL,33860172953LL,33877693796LL,33896077538LL,33914295415LL,33937308623LL,33951859662LL,33971471988LL,33990804218LL,34009856394LL,34026528468LL,34047369916LL,34063947217LL,34081324793LL,34103300592LL,34122505191LL,34138396955LL,34159237299LL,34172310268LL,34196295415LL,34212952224LL,34232957693LL,34251518224LL,34269667098LL,34288144112LL,34307456206LL,34323566579LL,34346919371LL,34363211500LL,34381404111LL,34395641438LL,34418021668LL,34435719132LL,34456288149LL,34474855471LL,34488640294LL,34512833004LL,34526740021LL,34548242474LL,34565512063LL,34581440685LL,34604395350LL,34617571178LL,34640866087LL,34656910809LL,34674785909LL,34691980863LL,34712781352LL,34729024164LL,34751445424LL,34763045716LL,34787488776LL,34803096271LL,34820973099LL,34838947916LL,34857021984LL,34877338899LL,34897652347LL,34912142598LL,34932992304LL,34947572338LL,34964707101LL,34987664365LL,35003060484LL,35021240315LL,35041782579LL,35055924687LL,35077674814LL,35093205497LL,35113275634LL,35131266832LL,35147523885LL,35167546187LL,35180265000LL,35205862981LL,35218625601LL,35237635968LL,35253509795LL,35279557446LL,35292159332LL,35307028618LL,35334091407LL,35345675742LL,35364176886LL,35380782228LL,35402422557LL,35415745734LL,35438422301LL,35454570810LL,35470636591LL,35490094047LL,35508231797LL,35521501895LL,35547885258LL,35561548162LL,35577989065LL,35595485032LL,35617457897LL,35632439427LL,35652964320LL,35666248781LL,35686845812LL,35702828944LL,35723412576LL,35737874917LL,35757305416LL,35774182994LL,35795187454LL,35807406934LL,35830945712LL,35845895303LL,35862965277LL,35879635173LL,35902821717LL,35914943533LL,35931882868LL,35951727309LL,35971543673LL,35985701810LL,36006720122LL,36021926020LL,36041546532LL,36055927096LL,36075636160LL,36088731268LL,36114997597LL,36130362916LL,36142230781LL,36161296774LL,36182199814LL,36197426642LL,36210177993LL,36238347185LL,36248362452LL,36269642045LL,36283985401LL,36300926460LL,36324087050LL,36334858816LL,36355228428LL,36373130947LL,36391626220LL,36405910511LL,36424097381LL,36445383067LL,36458701369LL,36476695829LL,36495263633LL,36510015189LL,36530533329LL,36547896696LL,36561190498LL,36582392941LL,36598755633LL,36616144983LL,36632817446LL,36650848448LL,36665948326LL,36683066669LL,36701381520LL,36721840999LL,36732744740LL,36756585157LL,36773512445LL,36786741455LL,36805125400LL,36822389034LL,36840209892LL,36856967908LL,36873520592LL,36890995627LL,36909320300LL,36926937289LL,36946779580LL,36956905568LL,36977379154LL,36996504150LL,37011460271LL,37029577296LL,37044028384LL,37060615576LL,37079063875LL,37098372292LL,37113333354LL,37131641082LL,37149010640LL,37163489696LL,37182175936LL,37200010095LL,37216899278LL,37231953121LL,37249139570LL,37267259121LL,37282591026LL,37304468305LL,37316942330LL,37332434312LL,37356661131LL,37365506139LL,37383502150LL,37406266679LL,37420425633LL,37435710751LL,37452520104LL,37471902916LL,37485431915LL,37505991943LL,37520174861LL,37535980969LL,37556667350LL,37571659861LL,37587217192LL,37605139697LL,37621945442LL,37636302481LL,37658505104LL,37673375814LL,37686707256LL,37707643960LL,37719680133LL,37740954012LL,37755200654LL,37772974770LL,37787094232LL,37807159791LL,37822672255LL,37840295782LL,37863959924LL,37870453357LL,37889993023LL,37900263223LL,37927308628LL,37942603226LL,37959061324LL,37967133804LL,37994420874LL,38002405702LL,38026470312LL,38037647967LL,38057184947LL,38074010544LL,38090173145LL,38104545572LL,38124927599LL,38134864643LL,38159738749LL,38175567966LL,38190093661LL,38202238933LL,38223444692LL,38238268131LL,38254662224LL,38275129143LL,38287803476LL,38300949871LL,38320687953LL,38339239714LL,38352885586LL,38372781919LL,38386571036LL,38401519359LL,38425001126LL,38433805232LL,38451403654LL,38469400554LL,38488997641LL,38497996300LL,38521841903LL,38535763115LL,38549562702LL,38566922520LL,38585841371LL,38597825343LL,38617238641LL,38635344482LL,38648539839LL,38667362672LL,38680667091LL,38701130986LL,38715491000LL,38733406515LL,38742915602LL,38764823150LL,38780827252LL,38798424449LL,38810007582LL,38828615697LL,38847915769LL,38864164231LL,38874239697LL,38895893324LL,38908924296LL,38927122423LL,38940938095LL,38955531280LL,38977700633LL,38992302403LL,39006702828LL,39023153377LL,39035982104LL,39061263950LL,39074472278LL,39087941704LL,39100994477LL,39118749930LL,39137882333LL,39158770698LL,39167872291LL,39182930225LL,39199224197LL,39222835745LL,39230318013LL,39248339753LL,39265112936LL,39283256917LL,39297887371LL,39312974438LL,39331458183LL,39343942882LL,39362023459LL,39380716770LL,39393987731LL,39407632998LL,39423438211LL,39442732145LL,39456850752LL,39477007571LL,39488984725LL,39505365475LL,39522464663LL,39540167666LL,39554980979LL,39566149293LL,39588328812LL,39600983301LL,39615113044LL,39634546836LL,39647868266LL,39662263786LL,39683330912LL,39696074238LL,39715675382LL,39726631932LL,39743905463LL,39762791551LL,39776325756LL,39791696699LL,39807831864LL,39826712362LL,39832818068LL,39857243374LL,39870126651LL,39889234795LL,39901333227LL,39920673646LL,39932503757LL,39952590626LL,39964318536LL,39979838908LL,40003811798LL,40009405519LL,40030904676LL,40040545086LL,40063014911LL,40077719778LL,40087388718LL,40108678723LL,40125256580LL,40138430897LL,40157539896LL,40169991162LL,40187570156LL,40203338837LL,40212673651LL,40232710848LL,40248843984LL,40263833678LL,40282522664LL,40293695314LL,40312026031LL,40327249843LL,40344918738LL,40355582507LL,40377210894LL,40390685701LL,40405203350LL,40417345013LL,40440303123LL,40449294450LL,40467787207LL,40487690524LL,40495883827LL,40512560775LL,40529202388LL,40540934282LL,40563183416LL,40577250330LL,40590395121LL,40606484613LL,40625213243LL,40636092978LL,40654719517LL,40669996316LL,40685331003LL,40702044782LL,40716682341LL,40729508947LL,40747104342LL,40760760035LL,40780950603LL,40791365470LL,40810257052LL,40823734905LL,40836170729LL,40856326873LL,40865580910LL,40885608268LL,40902167479LL,40917115429LL,40929500652LL,40948163496LL,40962485520LL,40977052331LL,40995759620LL,41007508568LL,41024804551LL,41038884650LL,41057937906LL,41067135467LL,41083893403LL,41099217570LL,41113509055LL,41137080727LL,41142301607LL,41163152143LL,41179801636LL,41189533527LL,41213316744LL,41218871725LL,41239467454LL,41252011021LL,41269455946LL,41285349461LL,41298765814LL,41314136612LL,41327957516LL,41344236157LL,41359289673LL,41380018773LL,41392548047LL,41402545988LL,41417220566LL,41435429436LL,41450237127LL,41470791937LL,41480620716LL,41496749879LL,41513608686LL,41530006263LL,41538287371LL,41555619241LL,41569747097LL,41586820042LL,41603870315LL,41616163358LL,41635534600LL,41647112127LL,41661924818LL,41681755299LL,41691797696LL,41705317549LL,41727771022LL,41739577316LL,41749466397LL,41768530695LL,41786200907LL,41800330966LL,41812344818LL,41826988684LL,41842801622LL,41859010213LL,41871587494LL,41891807737LL,41902290447LL,41919611435LL,41936193752LL,41945757677LL,41972634742LL,41971897405LL,41995044934LL,42006758925LL,42025413721LL,42036302695LL,42052576517LL,42069795532LL,42086230441LL,42098905278LL,42110702892LL,42128121715LL,42142303876LL,42161181919LL,42172367385LL,42187385061LL,42202051477LL,42221761603LL,42229917902LL,42249661183LL,42263087622LL,42272533881LL,42294526160LL,42306310833LL,42326235981LL,42331657129LL,42350736397LL,42366290428LL,42383919431LL,42389979730LL,42411424627LL,42434273394LL,42439001881LL,42454023568LL,42467652425LL,42483494915LL,42507586260LL,42508382077LL,42531924051LL,42541129984LL,42558455790LL,42574831237LL,42588957697LL,42600953621LL,42619572452LL,42629991055LL,42647287950LL,42662489085LL,42677921856LL,42689708000LL,42705686337LL,42724200416LL,42732803082LL,42750061913LL,42770234643LL,42774000213LL,42795669727LL,42805901285LL,42825405437LL,42840454713LL,42846414184LL,42872383529LL,42883365916LL,42896743724LL,42906222937LL,42927300463LL,42941684415LL,42959301252LL,42965550668LL,42982586684LL,43000774622LL,43016227565LL,43029815300LL,43047141694LL,43051696629LL,43070128754LL,43090104325LL,43102939495LL,43115239661LL,43136107349LL,43137707716LL,43162658554LL,43175935072LL,43183926177LL,43207004517LL,43212165592LL,43233850312LL,43246918127LL,43262215160LL,43277747055LL,43287492293LL,43306064525LL,43314528106LL,43337155590LL,43346446777LL,43369371057LL,43372157965LL,43385050046LL,43413768616LL,43417521161LL,43439605600LL,43449805581LL,43461977420LL,43474751233LL,43494158904LL,43503952261LL,43524615132LL,43538158894LL,43548070641LL,43561524960LL,43580829989LL,43598006400LL,43605235400LL,43619784571LL,43637585617LL,43649448215LL,43669419269LL,43680918924LL,43693254261LL,43710414488LL,43724538083LL,43735739327LL,43750401317LL,43765166724LL,43782546084LL,43794117295LL,43810309240LL,43821165952LL,43836350037LL,43851898043LL,43864823018LL,43879734557LL,43894419465LL,43910265156LL,43925339795LL,43941270914LL,43950327045LL,43961936223LL,43985979951LL,43999012772LL,44007772045LL,44024599868LL,44028906102LL,44057615173LL,44063882630LL,44079970870LL,44096074229LL,44104797115LL,44124869057LL,44137800009LL,44152372697LL,44163793437LL,44187525700LL,44190129262LL,44205418240LL,44225146821LL,44233242963LL,44250455444LL,44264088841LL,44279238121LL,44290114012LL,44309229299LL,44319379142LL,44338606745LL,44347357035LL,44364589077LL,44380383107LL,44390659888LL,44405576186LL,44421895986LL,44429549418LL,44444063460LL,44466892590LL,44481018244LL,44490841835LL,44504508401LL,44516056617LL,44535716335LL,44542290461LL,44560125004LL,44578366866LL,44591153722LL,44599313451LL,44620813016LL,44633948052LL,44644009548LL,44657257179LL,44672122847LL,44690294994LL,44702120244LL,44719648397LL,44724061727LL,44743435737LL,44762509373LL,44767751704LL,44785896555LL,44797727772LL,44814700399LL,44831333928LL,44839114982LL,44849010783LL,44871688002LL,44886454522LL,44892559830LL,44915706013LL,44918930064LL,44941518074LL,44958843407LL,44966219538LL,44979135602LL,44994159991LL,45008857679LL,45021575530LL,45036614689LL,45053307932LL,45063389892LL,45078631258LL,45091064824LL,45107882458LL,45122538519LL,45132656307LL,45148191392LL,45162445321LL,45169042565LL,45191478985LL,45203803442LL,45217370230LL,45226683960LL,45247241721LL,45259552378LL,45273433922LL,45285188357LL,45305337244LL,45312847218LL,45326529486LL,45339866311LL,45358568465LL,45366901283LL,45381996251LL,45400699034LL,45406763681LL,45425930466LL,45442231293LL,45449470051LL,45463218173LL,45477918605LL,45497608644LL,45503183048LL,45520580439LL,45533575690LL,45550734621LL,45558109335LL,45574817948LL,45589720423LL,45604772496LL,45618861193LL,45631178657LL,45643167781LL,45653364302LL,45675059334LL,45684017600LL,45697192232LL,45710076761LL,45727322676LL,45741717641LL,45758017510LL,45763067808LL,45783425295LL,45796794432LL,45803784748LL,45822732553LL,45832988694LL,45850441021LL,45870021761LL,45877039775LL,45888971252LL,45903823613LL,45916461149LL,45929859851LL,45948005383LL,45956336424LL,45969326451LL,45990859146LL,45997900082LL,46013612193LL,46023597415LL,46039074822LL,46054737458LL,46070949465LL,46078898723LL,46090259997LL,46114409678LL,46121600410LL,46132348174LL,46146459534LL,46166600765LL,46175275186LL,46188213024LL,46204944074LL,46217195602LL,46228077567LL,46239303067LL,46259610888LL,46268686774LL,46284960007LL,46293467068LL,46317341835LL,46321491194LL,46338180302LL,46352684291LL,46367275333LL,46380920583LL,46389909542LL,46399921823LL,46420038699LL,46435654852LL,46449617506LL,46455549452LL,46471625049LL,46486220602LL,46495818849LL,46515547842LL,46527395338LL,46538999149LL,46553134548LL,46570476646LL,46577360634LL,46596873003LL,46610516785LL,46614505847LL,46635326992LL,46644547239LL,46663402313LL,46673495539LL,46690278880LL,46696353379LL,46714439619LL,46728577399LL,46742840867LL,46758915073LL,46761674919LL,46780624498LL,46800611762LL,46802900743LL,46819011395LL,46836558708LL,46846719186LL,46866890511LL,46866791004LL,46887102951LL,46901928693LL,46910833612LL,46927850888LL,46947754035LL,46955294544LL,46966627733LL,46979315457LL,46997282775LL,47006424047LL,47024268455LL,47028331605LL,47047949198LL,47063489690LL,47072358127LL,47085578553LL,47105390754LL,47107210723LL,47127179159LL,47143010476LL,47156415566LL,47167717718LL,47177572777LL,47194432588LL,47204320334LL,47224138794LL,47230557584LL,47245190277LL,47258997887LL,47274770284LL,47287965501LL,47301533483LL,47304747233LL,47327167736LL,47339462729LL,47345245317LL,47372110591LL,47380790137LL,47388395511LL,47406350046LL,47416491241LL,47430057631LL,47446183498LL,47457037138LL,47469427941LL,47484214775LL,47494961886LL,47510986621LL,47522564723LL,47533037996LL,47550036371LL,47559329084LL,47580586199LL,47588090207LL,47604136540LL,47617208724LL,47628525743LL,47638467502LL,47655071769LL,47664136198LL,47682996063LL,47689930907LL,47709899887LL,47718010123LL,47733842328LL,47745852818LL,47758554964LL,47775869455LL,47782060241LL,47797811911LL,47812662253LL,47821635697LL,47837306048LL,47846178191LL,47865887922LL,47876502143LL,47893696983LL,47898741916LL,47918043086LL,47922649449LL,47947873068LL,47950143797LL,47971054815LL,47974107271LL,47993543670LL,48004926797LL,48023195078LL,48035498886LL,48042026187LL,48058555716LL,48071323751LL,48091937249LL,48096100535LL,48109858670LL,48126470976LL,48136169291LL,48146486615LL,48160345074LL,48172809636LL,48187478152LL,48205322258LL,48210201298LL,48223033430LL,48240238548LL,48259557952LL,48263816206LL,48282757592LL,48285388513LL,48305321231LL,48320467920LL,48332312548LL,48340854444LL,48351937073LL,48373488385LL,48385387083LL,48392344988LL,48405384071LL,48422466002LL,48431560559LL,48450539134LL,48459123439LL,48471956665LL,48480312353LL,48500619623LL,48511006650LL,48526306842LL,48532733055LL,48553326737LL,48556522749LL,48576798004LL,48585322835LL,48602954954LL,48613963328LL,48622699198LL,48642132271LL,48654796405LL,48664229754LL,48674515702LL,48691621033LL,48699755980LL,48720074181LL,48726452961LL,48742103063LL,48756326766LL,48762884094LL,48780890612LL,48793043292LL,48805663366LL,48819578459LL,48831250267LL,48840697478LL,48858402328LL,48870429209LL,48874835455LL,48895394244LL,48918897541LL,48916507083LL,48930300260LL,48949938775LL,48957913630LL,48966445246LL,48984734389LL,48998564187LL,49008293463LL,49021024629LL,49034749814LL,49042216679LL,49064479732LL,49074035303LL,49084862199LL,49097653883LL,49109124533LL,49127196818LL,49138849623LL,49140879759LL,49164246832LL,49175543069LL,49185217652LL,49206492986LL,49211337127LL,49220243912LL,49238815286LL,49251328868LL,49259477114LL,49276804447LL,49293168378LL,49302015566LL,49311658976LL,49323700027LL,49337229714LL,49352124440LL,49367154747LL,49371967524LL,49395204465LL,49402704096LL,49411035037LL,49429676961LL,49444239857LL,49443160870LL,49466286681LL,49485116922LL,49484666622LL,49505335738LL,49512812709LL,49528933564LL,49544699558LL,49552266532LL,49562767981LL,49582621845LL,49589231006LL,49601328071LL,49621170418LL,49625526312LL,49639273204LL,49653974351LL,49661472221LL,49690614346LL,49689415446LL,49701438386LL,49711857307LL,49730206230LL,49742058378LL,49747178263LL,49770397291LL,49775530155LL,49790164667LL,49810093877LL,49819742923LL,49827255941LL,49836074032LL,49857394670LL,49861113839LL,49887704144LL,49887945621LL,49899948410LL,49914284122LL,49939727509LL,49935502403LL,49956946432LL,49960086794LL,49981119065LL,49995749105LL,50004120931LL,50008417911LL,50035528509LL,50037593181LL,50048351420LL,50072891035LL,50075316039LL,50093974026LL,50101390386LL,50112648709LL,50132095772LL,50141008679LL,50148137965LL,50166150956LL,50180119826LL,50189121027LL,50203210339LL,50210998723LL,50225266276LL,50242551067LL,50248957637LL,50265776781LL,50277931787LL,50288847308LL,50305526098LL,50312550688LL,50328250844LL,50337155599LL,50345257220LL,50360891466LL,50379713879LL,50387728181LL,50400168534LL,50411988062LL,50427875136LL,50437664391LL,50447882327LL,50463376531LL,50478747898LL,50483285752LL,50498624534LL,50508311398LL,50527213894LL,50537692361LL,50543953345LL,50567333171LL,50568601679LL,50583803703LL,50601351199LL,50610527085LL,50618840889LL,50626935844LL,50652727694LL,50660596502LL,50672134367LL,50684791197LL,50693196576LL,50711849013LL,50720759592LL,50734476920LL,50748616691LL,50755191409LL,50764344160LL,50784354798LL,50787047929LL,50809500751LL,50820717090LL,50821735104LL,50846620863LL,50855137366LL,50874370318LL,50874870658LL,50890050704LL,50907265670LL,50912670776LL,50932594505LL,50938038205LL,50949920740LL,50966252832LL,50971545894LL,50993503677LL,51007548175LL,51017203036LL,51022737497LL,51038944621LL,51050768515LL,51064056573LL,51073911194LL,51083703500LL,51103923361LL,51112716853LL,51121545953LL,51133748952LL,51149240118LL,51160991667LL,51167857439LL,51185376708LL,51201083384LL,51203041274LL,51224712067LL,51234703805LL,51240787193LL,51254706037LL,51269774174LL,51278550379LL,51297210914LL,51303147965LL,51317682008LL,51337177682LL,51338994232LL,51352013810LL,51375321093LL,51370622357LL,51387269948LL,51404964433LL,51413955565LL,51426392556LL,51435599869LL,51447727187LL,51468972416LL,51475711741LL,51484867831LL,51497896378LL,51512419668LL,51521838873LL,51544997316LL,51543980870LL,51556140527LL,51574384486LL,51583616785LL,51596842565LL,51610933282LL,51610853560LL,51631644410LL,51646713673LL,51653807232LL,51670882884LL,51675989113LL,51695250100LL,51701773675LL,51715259349LL,51736291159LL,51737141776LL,51753432135LL,51758728352LL,51776592058LL,51789143264LL,51802823079LL,51816790673LL,51824505768LL,51831853936LL,51847009197LL,51861127892LL,51867797089LL,51885638547LL,51900977262LL,51901330122LL,51921418834LL,51932140212LL,51947843645LL,51949021792LL,51961747550LL,51984703172LL,51988680213LL,52004947038LL,52011727645LL,52034120046LL,52040922761LL,52048665650LL,52066442417LL,52075339675LL,52089103899LL,52097835766LL,52107218308LL,52124703057LL,52130780468LL,52149168179LL,52167356837LL,52163007016LL,52180726482LL,52196049617LL,52208522272LL,52218309433LL,52229702030LL,52238295063LL,52257768211LL,52264602677LL,52271708427LL,52286828636LL,52304030247LL,52317032335LL,52322650829LL,52338175812LL,52347033888LL,52362886052LL,52376696526LL,52382255704LL,52398486194LL,52405384911LL,52422570199LL,52425474938LL,52448054461LL,52457998729LL,52470788498LL,52477247906LL,52486493803LL,52501440807LL,52522626925LL,52521036883LL,52538344781LL,52551256074LL,52556027828LL,52574850320LL,52587219068LL,52599744091LL,52606551914LL,52619597066LL,52633845601LL,52647723998LL,52654296160LL,52666752127LL,52681673637LL,52688814259LL,52707259967LL,52714868607LL,52725494085LL,52737880081LL,52757192336LL,52764746750LL,52770013356LL,52788090966LL,52794467993LL,52809569478LL,52820347849LL,52835136497LL,52841355109LL,52859510179LL,52863590166LL,52883910871LL,52890497621LL,52907198582LL,52913268470LL,52925433326LL,52945557834LL,52938971041LL,52962021495LL,52978441239LL,52981381026LL,53006261417LL,53006481734LL,53028983006LL,53022928836LL,53043201957LL,53057646618LL,53073627479LL,53075006056LL,53084307543LL,53109514079LL,53109236127LL,53127832560LL,53139509976LL,53144076351LL,53167709196LL,53168822375LL,53181960624LL,53199093498LL,53209279404LL,53218496451LL,53230078889LL,53241473881LL,53249521641LL,53270885887LL,53272696442LL,53291803495LL,53300681075LL,53318050834LL,53317544561LL,53330960574LL,53349387426LL,53358108628LL,53371243180LL,53384886705LL,53391275876LL,53404514129LL,53415792183LL,53434786905LL,53440194232LL,53452565832LL,53464652192LL,53475504457LL,53486342184LL,53496642435LL,53508524573LL,53521826495LL,53536707268LL,53543230000LL,53551021733LL,53573056299LL,53580772992LL,53595539017LL,53596477072LL,53615365662LL,53623008647LL,53638174261LL,53654007714LL,53652617304LL,53671392929LL,53683974659LL,53702474787LL,53706021707LL,53710422877LL,53737297426LL,53741748916LL,53751369952LL,53759542244LL,53781390088LL,53786162727LL,53806143035LL,53799658944LL,53821810124LL,53834459268LL,53843556041LL,53858926816LL,53869220535LL,53878138329LL,53892385180LL,53900734004LL,53913857437LL,53922293707LL,53944910237LL,53947108684LL,53957922515LL,53973433553LL,53979150689LL,53994250338LL,54009823996LL,54016192550LL,54028938221LL,54038288845LL,54052040462LL,54058011788LL,54079716033LL,54080596429LL,54096482134LL,54114956876LL,54121970070LL,54127991934LL,54148037548LL,54152697596LL,54170505583LL,54176795789LL,54191353325LL,54194353149LL,54217844521LL,54225253205LL,54229850545LL,54250656968LL,54258612141LL,54267150688LL,54275232442LL,54296322450LL,54299497872LL,54321398747LL,54324025918LL,54341532560LL,54342831153LL,54358724761LL,54379093374LL,54376332567LL,54397553041LL,54409251465LL,54417751374LL,54432512721LL,54434490607LL,54459356700LL,54465977431LL,54472681377LL,54483167530LL,54494194920LL,54512733621LL,54519006039LL,54531637494LL,54543948759LL,54554683885LL,54554165716LL,54588738197LL,54583495297LL,54599396427LL,54617372614LL,54615990449LL,54634208459LL,54644326433LL,54655976969LL,54668012932LL,54674758406LL,54698063110LL,54700146875LL,54712560954LL,54724522062LL,54737982724LL,54750652970LL,54751828428LL,54768338925LL,54782365021LL,54793698681LL,54802449327LL,54811380927LL,54834709110LL,54835477463LL,54845776047LL,54866542521LL,54867857902LL,54880154713LL,54901165908LL,54897510430LL,54913319144LL,54937171358LL,54939575659LL,54948691430LL,54955993271LL,54973220270LL,54987674756LL,54996411154LL,55010098140LL,55016689744LL,55028058815LL,55038150570LL,55052206959LL,55060793600LL,55075709850LL,55090654967LL,55091374453LL,55111844194LL,55112590104LL,55137391826LL,55138579275LL,55150611990LL,55165630589LL,55175802891LL,55179590636LL,55203482187LL,55209817424LL,55215934980LL,55227524359LL,55246613207LL,55257996088LL,55260698180LL,55277959723LL,55287456830LL,55298370736LL,55307032803LL,55319184006LL,55335440799LL,55350355447LL,55349616917LL,55365493407LL,55374624770LL,55390872244LL,55403011011LL,55407734426LL,55415756888LL,55439130453LL,55445422912LL,55453206407LL,55466406860LL,55477116176LL,55490422386LL,55494537888LL,55518562196LL,55518317837LL,55529049210LL,55545538201LL,55560945091LL,55570071078LL,55577383648LL,55579808731LL,55602214751LL,55615065566LL,55625285145LL,55626495472LL,55648419964LL,55647850004LL,55669173262LL,55677464284LL,55693302373LL,55702486411LL,55710359963LL,55723505703LL,55730915272LL,55744916710LL,55759760345LL,55768235243LL,55773531594LL,55784546990LL,55802962346LL,55808430169LL,55824964950LL,55841018216LL,55834590976LL,55857853504LL,55865371107LL,55874975169LL,55890664903LL,55899360368LL,55909328183LL,55924603778LL,55933767952LL,55937376964LL,55961838070LL,55967865090LL,55973882983LL,55986561988LL,55996731030LL,56014474555LL,56025994717LL,56029839888LL,56043825780LL,56057459892LL,56067389878LL,56064898992LL,56092432206LL,56096659492LL,56118753190LL,56115344868LL,56138256490LL,56135209159LL,56150832030LL,56163585188LL,56182916357LL,56187893049LL,56194212395LL,56215127123LL,56213782313LL,56232332188LL,56245187874LL,56256839621LL,56264587164LL,56267934644LL,56292609484LL,56293922098LL,56313032395LL,56315478192LL,56330685465LL,56344386437LL,56345711803LL,56365187698LL,56371884162LL,56381151594LL,56395293527LL,56408814434LL,56421613160LL,56429596325LL,56437820445LL,56452699620LL,56461810808LL,56467066303LL,56484042419LL,56496007718LL,56502475716LL,56521298542LL,56523536998LL,56540528918LL,56549217969LL,56560037045LL,56577200009LL,56573202294LL,56593211770LL,56608655651LL,56612396465LL,56626330939LL,56643547085LL,56640050308LL,56655625256LL,56676666935LL,56677529127LL,56695513172LL,56701691051LL,56717686809LL,56716314735LL,56739269091LL,56739460314LL,56756662398LL,56763887654LL,56775935317LL,56791850613LL,56803169127LL,56809164838LL,56817756946LL,56835561722LL,56849276787LL,56853443232LL,56865517893LL,56872642906LL,56883447507LL,56904364642LL,56911994335LL,56912684155LL,56935748645LL,56941636464LL,56957599944LL,56955273507LL,56973972713LL,56981758167LL,56999134187LL,57007385500LL,57018991995LL,57024224398LL,57040160675LL,57044695029LL,57065090341LL,57080017303LL,57076199786LL,57088661992LL,57112444713LL,57111187853LL,57122847675LL,57130885690LL,57159686533LL,57152099556LL,57168440020LL,57185621419LL,57190729965LL,57197818691LL,57217305188LL,57219471371LL,57231753019LL,57235903310LL,57258507938LL,57269444765LL,57277794070LL,57291307057LL,57294312439LL,57310948685LL,57325982285LL,57327290404LL,57339242778LL,57352495529LL,57365904848LL,57369196420LL,57387084179LL,57392139643LL,57411822488LL,57419896086LL,57429522328LL,57435301077LL,57445657476LL,57463839121LL,57474196276LL,57480768946LL,57491206931LL,57503991483LL,57509200362LL,57523352954LL,57535068075LL,57552168598LL,57557257154LL,57561221239LL,57578139511LL,57585909598LL,57602217547LL,57614918700LL,57619202647LL,57628504143LL,57641880335LL,57659649972LL,57659574905LL,57679638472LL,57682058851LL,57690651404LL,57708483785LL,57728137918LL,57724246154LL,57740678224LL,57746500575LL,57764732334LL,57770351333LL,57788383449LL,57787087432LL,57795913958LL,57815039372LL,57825601281LL,57834079811LL,57849440542LL,57851501810LL,57874971755LL,57875790618LL,57886618427LL,57906901263LL,57901085176LL,57916686618LL,57933537627LL,57950827113LL,57955391457LL,57955183783LL,57986338004LL,57980073403LL,57989340886LL,58002856398LL,58022640890LL,58026011904LL,58032166355LL,58055632528LL,58060042500LL,58066681000LL,58085196339LL,58087719852LL,58101462080LL,58111806588LL,58125015688LL,58140091003LL,58141479909LL,58155575396LL,58163322452LL,58168994381LL,58193042849LL,58193777134LL,58208901117LL,58226993344LL,58220584656LL,58242841294LL,58252504738LL,58265226887LL,58261613004LL,58288224593LL,58288150278LL,58309900755LL,58307082562LL,58321295413LL,58335371036LL,58343950124LL,58357419474LL,58363304878LL,58386033587LL,58387195631LL,58399338557LL,58405160391LL,58415623541LL,58428245793LL,58444848782LL,58449160746LL,58466554403LL,58468274945LL,58490019798LL,58487283578LL,58505974023LL,58515938528LL,58530724199LL,58537966702LL,58546196954LL,58551289034LL,58577632620LL,58563158906LL,58589498336LL,58602977543LL,58609828635LL,58620737951LL,58636826224LL,58633123820LL,58650118776LL,58668230053LL,58669508230LL,58683948462LL,58688619759LL,58704528861LL,58711861872LL,58722321458LL,58747476883LL,58751669885LL,58756044574LL,58766881181LL,58780893948LL,58785984685LL,58805023844LL,58802457242LL,58821358455LL,58827658543LL,58832854325LL,58853366546LL,58862088367LL,58877587590LL,58886182535LL,58886243425LL,58902168056LL,58918217632LL,58929485143LL,58930997605LL,58949361143LL,58953675521LL,58964540656LL,58981674863LL,58987855172LL,58995698299LL,59009547594LL,59016671333LL,59032560318LL,59037986443LL,59058276825LL,59057476425LL,59070374040LL,59078005679LL,59095079847LL,59101580300LL,59105660152LL,59128922927LL,59136413239LL,59140870745LL,59152197677LL,59167227720LL,59180444136LL,59183295589LL,59203517992LL,59208845847LL,59213746972LL,59228808603LL,59240862014LL,59247164295LL,59264318214LL,59268746282LL,59273241361LL,59288778769LL,59297401244LL,59310407381LL,59323809877LL,59332961306LL,59342412777LL,59354592164LL,59364838521LL,59371204712LL,59382256339LL,59399608759LL,59397345289LL,59419562162LL,59430506940LL,59434635435LL,59449009186LL,59447161083LL,59472794408LL,59475704468LL,59482080519LL,59496624669LL,59512767659LL,59525488350LL,59529770993LL,59534040686LL,59551670733LL,59563888558LL,59567573122LL,59582123905LL,59593000638LL,59601571149LL,59609100674LL,59626650573LL,59622794995LL,59649712151LL,59645089956LL,59665362268LL,59673789080LL,59682295403LL,59701323361LL,59706862883LL,59712385950LL,59728110027LL,59733588176LL,59742005611LL,59763475312LL,59772991025LL,59778036704LL,59780201666LL,59794323823LL,59808195027LL,59817258152LL,59833915298LL,59840674300LL,59849633875LL,59862232222LL,59867890962LL,59875284566LL,59896354471LL,59904335408LL,59910704098LL,59911588831LL,59944951498LL,59928844509LL,59958961184LL,59961671950LL,59966033666LL,59986069582LL,59994944298LL,60008911742LL,60006354403LL,60022525995LL,60037292078LL,60052788075LL,60048942271LL,60075109573LL,60067254669LL,60092791510LL,60085104676LL,60109400262LL,60118259014LL,60124981967LL,60138624772LL,60146595624LL,60162676245LL,60172228478LL,60182333960LL,60183305473LL,60196224027LL,60208484659LL,60221669466LL,60226906386LL,60242941780LL,60249566845LL,60258661583LL,60268127138LL,60283519728LL,60294955673LL,60302536234LL,60310120429LL,60323807088LL,60322443100LL,60346337403LL,60357332358LL,60362050302LL,60374044467LL,60382683134LL,60388805917LL,60407678422LL,60413973743LL,60418380307LL,60434704101LL,60442099986LL,60455743189LL,60461322398LL,60477535376LL,60491808953LL,60493953371LL,60499494712LL,60520317268LL,60521936184LL,60530042745LL,60550090721LL,60551173476LL,60568749816LL,60578548256LL,60590693060LL,60589909222LL,60611395990LL,60619848713LL,60626032676LL,60638106838LL,60634927756LL,60670837914LL,60667014199LL,60675245410LL,60688404539LL,60706896485LL,60707298990LL,60713489965LL,60730506455LL,60747350645LL,60747462296LL,60753692454LL,60768609108LL,60776788379LL,60786001905LL,60805856109LL,60808951141LL,60820389916LL,60834481938LL,60838899037LL,60854788322LL,60864112431LL,60863582116LL,60880983311LL,60895465525LL,60906491151LL,60902867612LL,60919580335LL,60934819200LL,60944452593LL,60956462233LL,60956708885LL,60968450252LL,60984114680LL,60987274323LL,61007432731LL,61010592107LL,61018616761LL,61039727453LL,61041021386LL,61052098795LL,61065696152LL,61072230773LL,61078828433LL,61097570993LL,61094935518LL,61119163095LL,61128427484LL,61129350613LL,61141270221LL,61158160909LL,61167209291LL,61165225815LL,61187561406LL,61188529960LL,61204618913LL,61213945958LL,61222316983LL,61240957898LL,61246278006LL,61245926721LL,61271608523LL,61272375870LL,61287998602LL,61289938743LL,61302237689LL,61313122163LL,61333033157LL,61331746739LL,61344262815LL,61358016854LL,61364540452LL,61377860957LL,61383924804LL,61386633388LL,61406210813LL,61410107579LL,61432429544LL,61438753998LL,61449036414LL,61448937094LL,61463508227LL,61478378646LL,61480608606LL,61493096650LL,61507701965LL,61517383839LL,61525558355LL,61534941592LL,61548431850LL,61554379917LL,61563042774LL,61575735816LL,61586061925LL,61597598142LL,61604721242LL,61622529352LL,61628408961LL,61620836535LL,61651449302LL,61648349239LL,61670342902LL,61671514337LL,61681527576LL,61694978588LL,61708522291LL,61710947524LL,61728325755LL,61738254033LL,61743481718LL,61761584750LL,61755255878LL,61767851852LL,61791062302LL,61796513227LL,61801799042LL,61816583340LL,61827190477LL,61829177204LL,61850632522LL,61845889283LL,61869718238LL,61880131797LL,61888047966LL,61887004139LL,61903033997LL,61911320595LL,61925678241LL,61938621404LL,61944020541LL,61948369696LL,61963985375LL,61970736403LL,61986157282LL,61993715685LL,62005446161LL,62008644542LL,62029920928LL,62027680160LL,62043453224LL,62060261933LL,62062692286LL,62065783143LL,62088637285LL,62093610427LL,62100034830LL,62117415966LL,62117782529LL,62139639626LL,62139939942LL,62143400468LL,62171568000LL,62172230767LL,62186666485LL,62188964220LL,62199442124LL,62205107446LL,62226326004LL,62237489077LL,62234454917LL,62243059548LL,62258958228LL,62274675815LL,62281940312LL,62290500542LL,62304567077LL,62308626581LL,62323526051LL,62331453953LL,62343414150LL,62349535084LL,62357515134LL,62368905288LL,62379137522LL,62388945039LL,62397265987LL,62407227282LL,62421019968LL,62438034942LL,62427401892LL,62454921065LL,62453431631LL,62476001770LL,62474176086LL,62492753575LL,62495457127LL,62503526466LL,62522303704LL,62525479452LL,62537478825LL,62539782106LL,62559439115LL,62581195638LL,62561843109LL,62590769889LL,62598347618LL,62600647289LL,62617877559LL,62627751574LL,62642378483LL,62639191429LL,62650663187LL,62664207300LL,62678474028LL,62686354393LL,62704896411LL,62695686337LL,62714355852LL,62729425273LL,62727939656LL,62734740272LL,62755439668LL,62765271657LL,62776622289LL,62784092106LL,62792632882LL,62785919608LL,62815158586LL,62829275667LL,62827962088LL,62848051919LL,62844900140LL,62863068957LL,62869807108LL,62882444951LL,62890773204LL,62899586486LL,62916842571LL,62911508127LL,62926653449LL,62943662502LL,62953412383LL,62964025277LL,62967722254LL,62978944786LL,62984684713LL,62997857308LL,63002930139LL,63021685133LL,63023939023LL,63040495033LL,63046695791LL,63053447578LL,63071960124LL,63066172178LL,63091952928LL,63097670328LL,63101932109LL,63111631801LL,63130711868LL,63124216202LL,63151275676LL,63154396532LL,63163522240LL,63168747923LL,63192746417LL,63185827873LL,63205234031LL,63217635963LL,63219193064LL,63229405219LL,63243331540LL,63250792150LL,63258730849LL,63271035645LL,63270463660LL,63294764786LL,63296835518LL,63307746767LL,63322281824LL,63331147391LL,63333620106LL,63353424009LL,63350869385LL,63372998580LL,63380401732LL,63379554126LL,63400715388LL,63412489342LL,63418505272LL,63421730108LL,63439332371LL,63435937399LL,63459995586LL,63462630170LL,63474243903LL,63494582589LL,63482106853LL,63501626479LL,63518962132LL,63520875076LL,63535560481LL,63541785788LL,63544941505LL,63563399837LL,63573358754LL,63578411895LL,63587021446LL,63605165523LL,63603936263LL,63631579085LL,63629953107LL,63634731259LL,63652482075LL,63649470632LL,63664988827LL,63681644510LL,63683754615LL,63700820337LL,63695877850LL,63722259212LL,63729291910LL,63728897565LL,63750294116LL,63752005706LL,63764048373LL,63777253589LL,63782516328LL,63785213604LL,63808119829LL,63813454229LL,63818008308LL,63834239362LL,63842577602LL,63853882799LL,63855724051LL,63869569346LL,63878203839LL,63889845485LL,63897192827LL,63913373765LL,63907833621LL,63940519844LL,63941421561LL,63939884597LL,63961211331LL,63966077245LL,63978195190LL,63975338519LL,64000814915LL,63996938900LL,64024411358LL,64019167796LL,64030433648LL,64045228061LL,64050121585LL,64056675525LL,64079873251LL,64078519155LL,64097877347LL,64089495334LL,64108088257LL,64124887477LL,64136702642LL,64134100438LL,64150097185LL,64166602801LL,64162599093LL,64178071890LL,64181635310LL,64195266996LL,64214296325LL,64220924310LL,64219884365LL,64233833214LL,64251723888LL,64247672169LL,64266071274LL,64266499154LL,64281494770LL,64289954065LL,64307615532LL,64306424137LL,64324551967LL,64326287039LL,64334062583LL,64355240083LL,64353358335LL,64368950995LL,64385512749LL,64377899353LL,64404449014LL,64398485470LL,64430791402LL,64413557742LL,64444250957LL,64443715006LL,64453964287LL,64453160960LL,64478843475LL,64477861309LL,64491179375LL,64508134254LL,64504999688LL,64522394602LL,64527116631LL,64544714714LL,64544913204LL,64561986669LL,64570819926LL,64579161624LL,64588748174LL,64593036842LL,64605162314LL,64612651672LL,64629733870LL,64634426891LL,64639497703LL,64662125390LL,64657751672LL,64674241891LL,64690748351LL,64690060191LL,64700989939LL,64717221352LL,64719958975LL,64726717337LL,64741170144LL,64750747897LL,64757545266LL,64763960062LL,64772395338LL,64787023461LL,64798646295LL,64810076651LL,64816793670LL,64824059990LL,64832622503LL,64848575447LL,64857119497LL,64861168829LL,64875178327LL,64870844282LL,64896977838LL,64893930952LL,64913837016LL,64918860967LL,64932656690LL,64937215588LL,64945901307LL,64959749624LL,64965403616LL,64973244539LL,64988084026LL,64989858826LL,64999137438LL,65018319567LL,65020188334LL,65034329353LL,65037301975LL,65066075027LL,65058912378LL,65068888855LL,65081699133LL,65089409432LL,65089568826LL,65113423635LL,65119753034LL,65120427527LL,65143201840LL,65146583488LL,65157669042LL,65159068649LL,65174957886LL,65183425290LL,65197505269LL,65202448826LL,65212347166LL,65217213701LL,65233022760LL,65225782650LL,65262267300LL,65257568088LL,65274860159LL,65275145706LL,65291346948LL,65293345303LL,65306400031LL,65312894946LL,65328522268LL,65329068397LL,65339574367LL,65352013166LL,65362568783LL,65371618517LL,65379595493LL,65396292933LL,65403796131LL,65404401617LL,65425930812LL,65422223561LL,65434470141LL,65447663748LL,65462715000LL,65460813377LL,65479440849LL,65481872656LL,65489718187LL,65509157704LL,65505173102LL,65521324124LL,65530424459LL,65538703713LL,65561534518LL,65560728688LL,65559591759LL,65575759704LL,65588726020LL,65595408092LL,65610250211LL,65612891842LL,65623856368LL,65626709228LL,65660462513LL,65643786085LL,65657844307LL,65672218443LL,65680276723LL,65693262200LL,65692783757LL,65712746496LL,65717206746LL,65730665133LL,65735707996LL,65750279735LL,65764367621LL,65761919452LL,65770030198LL,65787879410LL,65790934716LL,65800254534LL,65808110320LL,65829002147LL,65836313472LL,65826880242LL,65848114686LL,65855717559LL,65866907216LL,65876479382LL,65883368575LL,65897360151LL,65905122758LL,65923040440LL,65917443567LL,65933849256LL,65940852862LL,65950027874LL,65958024985LL,65971819912LL,65985791899LL,65983488806LL,65998363509LL,66010227819LL,66012818985LL,66024688985LL,66034705356LL,66043065620LL,66061651103LL,66063199279LL,66074667187LL,66078668491LL,66083910431LL,66101606269LL,66103087165LL,66128130629LL,66126812602LL,66139050497LL,66142283268LL,66157083556LL,66163054628LL,66167206132LL,66182815662LL,66208266719LL,66188515662LL,66218409412LL,66215254188LL,66226264052LL,66243728674LL,66251880978LL,66255471544LL,66258776986LL,66279733369LL,66279111445LL,66304553021LL,66302059216LL,66313065803LL,66325722706LL,66324991362LL,66353204531LL,66351276620LL,66355771483LL,66366465985LL,66378830620LL,66382298889LL,66393256802LL,66412047778LL,66416926148LL,66420655148LL,66437026490LL,66435696914LL,66456371501LL,66454322001LL,66466041239LL,66483085020LL,66489009715LL,66495493517LL,66513356393LL,66510413063LL,66524303240LL,66538987169LL,66552648848LL,66546953927LL,66561771500LL,66565009969LL,66577400530LL,66585117227LL,66606236614LL,66611621332LL,66613675505LL,66632155485LL,66636214759LL,66639374689LL,66652767806LL,66659740729LL,66678232966LL,66680553650LL,66684813477LL,66703035919LL,66709958911LL,66731882525LL,66722811742LL,66733648385LL,66744370638LL,66754950773LL,66771452066LL,66768136944LL,66783755034LL,66799142815LL,66802827857LL,66809207815LL,66815498645LL,66836335154LL,66827033016LL,66849192614LL,66859522318LL,66862087986LL,66880136969LL,66880772048LL,66899277019LL,66892849004LL,66915506891LL,66921667562LL,66931613309LL,66936854141LL,66945606856LL,66959404791LL,66964393168LL,66973871543LL,66986430311LL,66989536934LL,67003589993LL,67022670737LL,67013057377LL,67025962118LL,67050122814LL,67042944910LL,67054248484LL,67067707453LL,67075639395LL,67088442126LL,67094874407LL,67103460841LL,67109055727LL,67122042479LL,67128202945LL,67141095565LL,67143473445LL,67171757619LL,67167608740LL,67167519395LL,67191532571LL,67199590362LL,67197099164LL,67209761804LL,67230194687LL,67226864925LL,67241054618LL,67247410906LL,67250576046LL,67267820658LL,67280543723LL,67288910957LL,67296057645LL,67298316526LL,67317316921LL,67319667663LL,67334589279LL,67339462327LL,67350360323LL,67360029168LL,67363749210LL,67383000413LL,67376063461LL,67402560082LL,67403444013LL,67410911755LL,67424856800LL,67434984580LL,67440321703LL,67446722845LL,67468195851LL,67462197134LL,67477403047LL,67470444880LL,67500851920LL,67503861356LL,67528632994LL,67511446973LL,67535676585LL,67535291863LL,67549814220LL,67550237124LL,67571208036LL,67576309811LL,67583290864LL,67600083050LL,67598467475LL,67615225815LL,67622317883LL,67646796471LL,67629051198LL,67639444446LL,67659590403LL,67671096972LL,67672111748LL,67676971078LL,67690654542LL,67724170374LL,67709131600LL,67716421373LL,67726058526LL,67734360885LL,67754104608LL,67767360170LL,67764396838LL,67777140457LL,67788570523LL,67782317749LL,67796465448LL,67822991650LL,67822552634LL,67833253754LL,67831146435LL,67848252375LL,67864958090LL,67866195846LL,67872844975LL,67887516833LL,67889307038LL,67893778977LL,67911158343LL,67929098211LL,67924837827LL,67947204761LL,67949623431LL,67956345289LL,67960502314LL,67977721774LL,67980003948LL,67988710291LL,67997452959LL,68015011573LL,68013538892LL,68025871589LL,68045987426LL,68048005462LL,68045562002LL,68073104669LL,68077856146LL,68087258909LL,68084216537LL,68106448192LL,68104914741LL,68110386661LL,68126803179LL,68138819563LL,68153314701LL,68158358641LL,68160602338LL,68173067631LL,68174671217LL,68190558601LL,68196845493LL,68214162161LL,68227030849LL,68219014499LL,68232324710LL,68248280809LL,68250801900LL,68264103872LL,68267800318LL,68277737308LL,68300504635LL,68294051528LL,68296838180LL,68315357681LL,68335384704LL,68331699510LL,68343130629LL,68350236264LL,68355799158LL,68367625915LL,68380849964LL,68387953884LL,68392930617LL,68409084693LL,68413202909LL,68422972888LL,68434278070LL,68444777089LL,68444735416LL,68451425316LL,68470091426LL,68473152489LL,68494424527LL,68490343832LL,68499786367LL,68515899379LL,68526105278LL,68532370307LL,68537012461LL,68549764752LL,68557435075LL,68571380321LL,68570939402LL,68586137837LL,68589230860LL,68597137682LL,68610807514LL,68629062220LL,68621746656LL,68645028867LL,68646803049LL,68660917823LL,68661632329LL,68666275266LL,68677804362LL,68700384992LL,68697618125LL,68699849627LL,68716172774LL,68730265723LL,68741378826LL,68742475986LL,68761162602LL,68757957610LL,68773143312LL,68776801811LL,68789794128LL,68796569769LL,68807749438LL,68817499775LL,68824209396LL,68836995280LL,68845138161LL,68840534470LL,68865475091LL,68860112938LL,68884254735LL,68884667789LL,68892450513LL,68912629623LL,68912067778LL,68936358872LL,68931824653LL,68929356345LL,68949081416LL,68956251120LL,68966574995LL,68979387337LL,68980141846LL,68989533673LL,69008355438LL,69003009766LL,69028964340LL,69017067051LL,69040529679LL,69044579562LL,69057331171LL,69072735512LL,69065425448LL,69088451974LL,69091635913LL,69094914564LL,69104138986LL,69119560145LL,69127485770LL,69135630540LL,69150532198LL,69150155639LL,69163158623LL,69158173633LL,69195506477LL,69174413280LL,69204006159LL,69213069844LL,69214437250LL,69218477584LL,69230925170LL,69245518535LL,69254843599LL,69258195033LL,69270505000LL,69265914102LL,69295767894LL,69288801799LL,69317830509LL,69310841546LL,69323690718LL,69320446598LL,69333117767LL,69342212902LL,69360080386LL,69364806698LL,69374377583LL,69379965747LL,69399756708LL,69406073863LL,69398208296LL,69418348509LL,69426725177LL,69436049781LL,69446175469LL,69452680200LL,69456741472LL,69482357535LL,69469819967LL,69484507929LL,69506592939LL,69508312882LL,69513872900LL,69527917192LL,69535108963LL,69531507928LL,69544311741LL,69571495937LL,69561846932LL,69579330250LL,69584029165LL,69597769484LL,69599524558LL,69615450171LL,69616990035LL,69634911852LL,69634145905LL,69644671186LL,69657214609LL,69659228669LL,69680555641LL,69676369757LL,69691035091LL,69694857832LL,69711087151LL,69721894901LL,69726545635LL,69732380690LL,69747006225LL,69747675094LL,69762610750LL,69772143221LL,69780647742LL,69782525091LL,69795296814LL,69804512973LL,69812825120LL,69823518554LL,69824957333LL,69840258548LL,69845056260LL,69868958688LL,69867664004LL,69869034206LL,69889478924LL,69884441168LL,69907985010LL,69900071210LL,69928580984LL,69918879951LL,69940880679LL,69953749319LL,69948286698LL,69957708457LL,69980039785LL,69979057450LL,69989362295LL,69987072705LL,70009268751LL,70011144679LL,70026796307LL,70032017337LL,70041587226LL,70051442883LL,70051138049LL,70075680718LL,70074001933LL,70081276440LL,70097004671LL,70099710527LL,70099327845LL,70115116683LL,70145087735LL,70140602036LL,70142579247LL,70151144964LL,70165752556LL,70170593958LL,70180376112LL,70183129259LL,70193881751LL,70203503813LL,70225959333LL,70220038807LL,70232324288LL,70232401880LL,70254080955LL,70256487527LL,70271380234LL,70273568765LL,70285239519LL,70293627865LL,70302521632LL,70314449635LL,70317636482LL,70326940096LL,70333195611LL,70350009668LL,70357487880LL,70360315232LL,70372137034LL,70377390518LL,70384531940LL,70399824673LL,70409060988LL,70415950567LL,70428722151LL,70418626893LL,70444782152LL,70455128012LL,70455229707LL,70476446178LL,70473215301LL,70489795672LL,70492462342LL,70502632775LL,70505403661LL,70523266184LL,70529263157LL,70530068700LL,70550140559LL,70545973962LL,70555865429LL,70582711782LL,70581902143LL,70579552246LL,70603236102LL,70604504309LL,70622199969LL,70613478305LL,70638079020LL,70642302396LL,70638592202LL,70662306138LL,70667990774LL,70678482902LL,70676488343LL,70691762509LL,70705318494LL,70719041970LL,70712711028LL,70724510778LL,70730521015LL,70740086854LL,70753961098LL,70754146431LL,70778438069LL,70777731564LL,70795396023LL,70783594649LL,70808574663LL,70810709039LL,70832798943LL,70832283669LL,70832860727LL,70848101172LL,70856088067LL,70870683710LL,70871576695LL,70880446240LL,70892509730LL};
bool check(ll x)
{
    for(int i=1;i<=m;i++){
        x-=x/p[i];
    }
    return x>=k;
}
void cal(ll x)
{
    if(x%2500000<=1250000){
        ll sum=0;
        for(int i=1;i<=x/2500000;i++){
            sum+=pre[i];
        }
        ll l=(x/2500000)*2500000+1,r=x;
        for(int i=0;i<r-l+1;i++)ans[i]=1;
        for(ll j=2;j*j<=r;j++){
            for(ll k=max(j,(l+j-1)/j)*j-l;k<r-l+1;k+=j){
                ans[k]=j;
            }
        }
        for(int i=0;i<r-l+1;i++){
            sum+=ans[i];
        }
        printf("%lld\n",sum);
    }else{
        ll sum=0;
        for(int i=1;i<=(x+2499999)/2500000;i++){
            sum+=pre[i];
        }
        ll l=x+1,r=(x+2499999)/2500000*2500000;
        for(int i=0;i<r-l+1;i++)ans[i]=1;
        for(ll j=2;j*j<=r;j++){
            for(ll k=max(j,(l+j-1)/j)*j-l;k<r-l+1;k+=j){
                ans[k]=j;
            }
        }
        for(int i=0;i<r-l+1;i++){
            sum-=ans[i];
        }
        printf("%lld\n",sum);
    }
    
}
void work()
{

    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%lld",&p[i]);
    }
    if(!check(n)){
        printf("-1\n");return;
    }
    ll l=k,r=n;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cal(l);
}
int main()
{
    //double time=clock();
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
    //printf("%f\n",clock()-time);
}

D.Distinct Sub-palindromes

lmj (01:04:26) +1

题意

求长度为n的字符串中,回文子串最少的串的数量

题解

1个的时候显然为26,2个的时候所有都是2个回文子串,$26*26$,3个的时候所有都是3个回文子串,$26*26*26$,四个的时候,考虑类似于abca这样的情况,只有3个回文子串,这样的情况只有$26*25*24$,5个的时候abcab,后面同理。所以得到结果 前3个为26的i次方,后面的都为$26*25*24$

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    int n;
    scanf("%d",&n);
    if(n<=3){
        printf("%lld\n",qpow(26,n));
    }else{
        printf("%lld\n",15600);
    }
    
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Fibonacci Sum

wrf (01:41:20) +3

题意

已知:

$$ F_i=\left\{ \begin{aligned} &0 &i=0 \\ &1 &i=1 \\ &F_{i-1}+F_{i-2} &otherwise \end{aligned} \right. $$

求:

$$ (F_0)^K+(F_C)^K+(F_{2C})^K+\cdots+(F_{NC})^K \mod 10^9+9 $$

题解

做法

通过一系列预处理,计算

$$ ({1 \over \sqrt{5}})^K\sum_{j=0}^K(-1)^j\dbinom{K}{j}\Sigma \qquad \Sigma=\left\{ \begin{aligned} &N+1 &t=1 \\ &{1-t^{N+1} \over 1-t} &otherwise \end{aligned} \right. $$

即可。

证明

$$ \begin{aligned} S&=\sum_{i=0}^N (F_{iC})^K \\ &=\sum_{i=0}^N ({1 \over \sqrt{5}}(p^{iC}-q^{iC}))^K &p={1+\sqrt 5 \over 2},q={1-\sqrt 5 \over 2}\\ &=({1 \over \sqrt{5}})^K\sum_{i=0}^N(P^i-Q^i)^K &P=p^C,Q=q^C \\ &=({1 \over \sqrt{5}})^K\sum_{i=0}^N\sum_{j=0}^K (-1)^j\dbinom{K}{j}P^{i(K-j)}Q^{ij} \\ &=({1 \over \sqrt{5}})^K\sum_{j=0}^K(-1)^j\dbinom{K}{j}\sum_{i=0}^N t^i &t=P^{K-j}Q^j \\ &=({1 \over \sqrt{5}})^K\sum_{j=0}^K(-1)^j\dbinom{K}{j}\Sigma &\Sigma=\left\{ \begin{aligned} &N+1 &t=1 \\ &{1-t^{N+1} \over 1-t}&otherwise \end{aligned} \right. \end{aligned} $$

实现细节

因为 $5$ 是 $10^9+9$ 的二次剩余,所以这个方法才可做。
有个 $O(n)$ 预处理任意数列逆元的小技巧:预处理前缀积、后缀积、数列中所有数积的逆元,使用的时候用逆元乘上相应的前后缀积即可。

时间复杂度

$O(T(K+\log M))$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const int mod=1000000009;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const ll sq5=383008016LL;
const ll re2=500000005LL;

ll qpow(ll a,ll b,int m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
        {
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1; 
    } 
    return ans;
}

void exgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }

    exgcd(b,a%b,x,y);
    
    ll k=x;
    x=y;
    y=k-(a/b)*y;
    
    return ;
}

ll inv(ll a,ll p)
{
    if(a==0)
    {
        return 0LL;
    }
    ll x,y;

    exgcd(a,p,x,y);

    return (x%p+p)%p;
}

ll rev[N];

int main(void)
{
    const ll resq5=inv(sq5,mod);
    const ll p=(1LL+sq5)*re2%mod,q=(1LL+mod-sq5)*re2%mod;

    rev[0]=0LL;
    rev[1]=1LL;
    for(ll i=2;i<N;i++)
    {
        rev[i]=(mod-mod/i)*rev[mod%i]%mod;
    }

    for(int _=read();_>0;_--)
    {
        ll n=read(),c=read(),k=read();
        ll pc=qpow(p,c,mod),qc=qpow(q,c,mod);
        ll inpc=inv(pc,mod);
        ll pnc=qpow(pc,n+1,mod),qnc=qpow(qc,n+1,mod);
        ll inpnc=inv(pnc,mod);
        ll qqq=(n+1)%mod;

        vector<ll> ck(k+1),t(k+1),tn(k+1),d(k+1),prd(k+1),ind(k+1);
        ck[0]=1;
        
        for(int i=0;i<k;i++)
        {
            ck[i+1]=ck[i]*(k-i)%mod*rev[i+1]%mod;
        }
        t[0]=qpow(pc,k,mod);
        for(int i=0;i<k;i++)
        {
            t[i+1]=t[i]*inpc%mod*qc%mod;
        }
        tn[0]=qpow(pnc,k,mod);
        for(int i=0;i<k;i++)
        {
            tn[i+1]=tn[i]*inpnc%mod*qnc%mod;
        }

        for(int i=0;i<=k;i++)
        {
            d[i]=(1LL+mod-t[i])%mod;
            prd[i]=(i==0?1LL:prd[i-1])*(d[i]==0?1:d[i])%mod;
        }
        ll tmp=inv(prd[k],mod);
        for(int i=k;i>=0;i--)
        {
            ind[i]=tmp*(i==0?1:prd[i-1])%mod;
            tmp=tmp*(d[i]==0?1:d[i])%mod;
        }

        ll ans=0;
        for(int i=0;i<=k;i++)
        {
            if(t[i]!=1)
            {
                ll u=(1LL+mod-tn[i]);
                u=(u>=mod?u-mod:u);
                ans+=(i%2?mod-ck[i]:ck[i])*u%mod*ind[i]%mod;
                ans=(ans>=mod?ans-mod:ans);
            }
            else
            {
                ans+=(i%2?mod-ck[i]:ck[i])*qqq%mod;
                ans=(ans>=mod?ans-mod:ans);
            }
        }
        
        ans=qpow(resq5,k,mod)*ans%mod;
        printf("%lld\n",ans);
    }
    
    return 0;
}

F.Finding a MEX

zyj (赛后) +2

题意

给你一个n个点m条边的无向连通图,有两个操作,分别是修改每个点的点权和查询每个点连出去所有点的MEX值$(n,m \leq 10^5)$

题解

按照度数分块,把点分为度数大于1000和小于1000的,对于小于1000的点每次暴力查询答案,大于1000的每个点维护一个set,set里维护的是这个点周围没出现的所有点,那么显然每次询问答案就是s[u].begin()。
当然还有一个显然的发现是,每个set里只用存小于等于deg[u]的值即可,再大的值就没意义了,并且set的个数不会超过100个,每个set内最多100000个点,复杂度可以接受。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int lim=1000;
int n,m,a[maxn],de[maxn];
int bi[1010];
vector<int> g[maxn],mp[maxn];
set<int> s[maxn];
map<int,int> id,cnt[110];
void fun(){
    int op,u;scanf("%d%d",&op,&u);
    if(op==1){
        int x;scanf("%d",&x);
        for(auto v:mp[u]){
            if(x<=de[v]) cnt[id[v]][x]++;
            if(a[u]<=de[v]) cnt[id[v]][a[u]]--;
            if(cnt[id[v]][x]>0){
                if(s[v].find(x)!=s[v].end()) s[v].erase(x);
            }
            if(cnt[id[v]][a[u]]==0) s[v].insert(a[u]);
        }a[u]=x;
    }
    else{
        if(de[u]<lim){
            memset(bi,0,sizeof(bi));
            for(auto v:g[u]) if(a[v]<=lim) bi[a[v]]=1; 
            rep(i,0,lim) if(!bi[i]){printf("%d\n",i);break;}
        }
        else{
            printf("%d\n",*s[u].begin());
        }
    }
}
void solve(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]);
    rep(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);de[u]++;de[v]++;
    }int tot=0;
    rep(i,1,n) for(auto v:g[i]) if(de[v]>=lim) mp[i].pb(v);
    rep(i,1,n) if(de[i]>=lim){
        id[i]=++tot;
        rep(j,0,de[i]) s[i].insert(j);
    }
    rep(i,1,n) if(de[i]>=lim){
        for(auto v:g[i]) if(a[v]<=de[i]){
            s[i].erase(a[v]);
            cnt[id[i]][a[v]]++;
        }
    }
    int q;scanf("%d",&q);
    while(q--) fun();
    rep(i,1,n) id.clear(),g[i].clear(),mp[i].clear(),s[i].clear(),de[i]=0;
    rep(i,1,100) cnt[i].clear();
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

H.Integral Calculus

wrf(赛后)

题意

求:

$$ \int_0^{+\infty} {\tau^{-4N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau \over (\int_0^{+\infty} {\tau^{-2N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau)^2 $$

题解

做法

首先预处理前 $4n$ 项伯努利数。
原式有:

$$ {\int_0^{+\infty} {\tau^{-4N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau \over (\int_0^{+\infty} {\tau^{-2N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau)^2}=-2n\cdot{{B_{4n}} \over {B_{2n}}^2} $$

代入即可。

证明

首先有:

$$ \begin{aligned} \int_0^{+\infty} {\tau^{-n-2} \over e^{1 \over \tau}-1} \mathrm{d}\tau &= \int_0^{+\infty} {t^n \over 1-e^t}\mathrm{d} t &t\tau=1\\ &=\int_0^{+\infty} t^n \lim_{m \rightarrow \infty}{1-e^{-mt} \over 1-e^t}\mathrm{d}t \\ &=\int_0^{+\infty} t^n \sum_{i=0}^\infty e^{-it} \mathrm{d}t \\ &=\sum_{i=0}^\infty\int_0^{+\infty} t^n e^{-it} \mathrm{d}t \\ \end{aligned} $$

考虑如下积分(拉普拉斯变换):

$$ \begin{aligned} F(n)&=\int_0^{+\infty} t^n e^{-it} \mathrm{d}t \\ &=\left.{{1 \over i}t^n e^{-it}}\right|_0^{+\infty}-{n \over i}\int_0^{+\infty} t^{n-1} e^{it} \mathrm{d}t \\ &=-{n \over i}F(n-1) \\ &=-{n! \over i^n}F(0)={n! \over i^{n+1}} \end{aligned} $$

所以:

$$ \int_0^{+\infty} {\tau^{-n-2} \over e^{1 \over \tau}-1} \mathrm{d}\tau =n!\sum_{i=0}^\infty{1 \over i^{n+1}}=n!\zeta(n+1) $$

那么原式可化为:

$$ {\int_0^{+\infty} {\tau^{-4N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau \over (\int_0^{+\infty} {\tau^{-2N-1} \over e^{1 \over \tau}-1} \mathrm{d}\tau)^2}={(4n-1)!\zeta(4n) \over ((2n-1)!\zeta(2n))^2} $$

又由黎曼 $\zeta$ 函数与伯努利数 $B_n$ 的关系:

$$ \zeta(2n)={B_{2n}(-1)^{n+1}(2\pi)^{2n} \over 2(2n)!} $$

得到所要证的式子:

$$ {(4n-1)!\zeta(4n) \over ((2n-1)!\zeta(2n))^2}={(4n-1)!{-B_{4n}(2\pi)^{4n} \over 2(4n)!} \over ((2n-1)!{B_{2n}(-1)^{n+1}(2\pi)^{2n} \over 2(2n)!})^2}=-2n\cdot{{B_{4n}} \over {B_{2n}}^2} $$

实现细节

$10^9+9$ 这个模数不够好,所以得用 MTT。

吐槽

这个模板本地要预处理十几秒,交上去莫名就过了。

时间复杂度

$O(n \log^2 n)$

代码

#include<cstdio>
#include<algorithm>
#include<cmath>

#define R register
#define ll long long
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
ll read(){
    R ll res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=2000000,K=400005,P=1e9+9;const double Pi=acos(-1.0);
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
    return res;
}
struct cp{
    double x,y;
    cp(){}
    cp(R double xx,R double yy):x(xx),y(yy){}
    inline cp operator +(const cp &b)const{return cp(x+b.x,y+b.y);}
    inline cp operator -(const cp &b)const{return cp(x-b.x,y-b.y);}
    inline cp operator *(const cp &b)const{return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
}w[2][N];
int r[N],inv[N],ifac[N],fac[N],B[N],A[N],c[N],d[N],lim,l,n,k,res,nw;
inline void init(int len){
    lim=1,l=0;while(lim<len)lim<<=1,++l;
    fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
void FFT(cp *A,int ty){
    fp(i,0,lim-1)if(i<r[i])swap(A[i],A[r[i]]);
    for(R int mid=1;mid<lim;mid<<=1)
        for(R int j=0;j<lim;j+=(mid<<1))
            fp(k,0,mid-1){
                R cp x=A[j+k],y=A[j+k+mid]*w[ty][mid+k];
                A[j+k]=x+y,A[j+k+mid]=x-y;
            }
    if(!ty){
        R double k=1.0/lim;
        fp(i,0,lim-1)A[i].x*=k;
    }
}
void MTT(int *a,int *b,int len,int *c){
    init(len<<1);
    static cp A[N],B[N],C[N],D[N],E[N],G[N],F[N];
    fp(i,0,len-1){
        A[i].x=a[i]>>15,B[i].x=a[i]&32767,
        C[i].x=b[i]>>15,D[i].x=b[i]&32767,
        A[i].y=B[i].y=C[i].y=D[i].y=0;
    }fp(i,len,lim-1)A[i]=B[i]=C[i]=D[i]=cp(0,0);
    FFT(A,1),FFT(B,1),FFT(C,1),FFT(D,1);
    fp(i,0,lim-1)E[i]=A[i]*C[i],F[i]=A[i]*D[i]+B[i]*C[i],G[i]=B[i]*D[i];
    FFT(E,0),FFT(F,0),FFT(G,0);
    fp(i,0,lim-1)c[i]=(((ll)(E[i].x+0.5)%P<<30)+((ll)(F[i].x+0.5)<<15)+((ll)(G[i].x+0.5)))%P;
}
void Inv(int *a,int *b,int len){
    if(len==1)return b[0]=ksm(a[0],P-2),void();
    Inv(a,b,len>>1);
    MTT(a,b,len,c),MTT(c,b,len,d);
    fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),d[i]);
}
inline void init(){
    for(R int i=1;i<(1<<20);i<<=1)fp(k,0,i-1)
        w[1][i+k]=cp(cos(Pi*k/i),sin(Pi*k/i)),w[0][i+k]=cp(cos(Pi*k/i),-sin(Pi*k/i));
    B[0]=ifac[0]=ifac[1]=inv[0]=inv[1]=fac[0]=fac[1]=1;
    fp(i,2,K+5){
        fac[i]=mul(fac[i-1],i),
        inv[i]=mul(P-P/i,inv[P%i]),
        ifac[i]=mul(ifac[i-1],inv[i]);
    }
    fp(i,0,K)A[i]=ifac[i+1];
    Inv(A,B,1<<19);
    fp(i,0,K)B[i]=mul(B[i],fac[i]);
}

ll qpow(ll a,ll b,int m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
        {
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1; 
    } 
    return ans;
}
int main() {
 
    init();
    int n;
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        scanf("%d", &n);
        // printf("%d %d %d %d",B[2*n],B[4*n],B[2*n-1],B[4*n-1]);
        printf("%lld\n", 1ll*(P-2)*n%P*B[4*n]%P*qpow(B[2*n],P-2,P)%P*qpow(B[2*n],P-2,P)%P);
    }
    return 0;
}

I.Leading Robots

lmj (03:00:51) +8

题意

给n辆车的位置和加速度,求有多少辆车可能在唯一的最前面,如果有两辆车同时在最前面则不算

题解

先考虑去掉不可能的和去重,将车以位置为第一优先级,以速度为第二优先级排序,不断将车加入队列,如果这辆车和队列中的那辆完全相同,打一个重复标记(不能直接删,因为有可能前面有车在没达到头的时候被他超,删了有可能导致答案计算不准确),如果这辆车的速度小于等于队列中的这辆车,那么显然不可能超过,不计入,否则计入。
然后使用单调栈,每次考虑当前车能否在前一辆车超过再前一辆之前超过前一辆车,然后对栈进行修改即可,最后计算答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct node
{
    ll p;
    ll a;
}b[N];
bool cmp(node x,node y)
{
    if(x.p!=y.p)return x.p>y.p;
    else return x.a>y.a;
}
int q[N];
int vis[N];
int ans[N];
int q2[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&b[i].p,&b[i].a);
        vis[i]=0;
        ans[i]=0;
    }
    sort(b+1,b+n+1,cmp);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!cnt){
            q[++cnt]=i;
        }else{
            if(b[q[cnt]].p==b[i].p&&b[q[cnt]].a==b[i].a){
                vis[q[cnt]]=1;
                continue;
            }
            if(b[i].a<=b[q[cnt]].a){
                continue;
            }else{
                q[++cnt]=i;
            }
        }
    }
    //printf("%d\n",cnt);
    if(cnt==1){
        if(vis[q[1]]){
            printf("0\n");
        }else{
            printf("1\n");
        }
        return;
    }
    int tot=0;
    q2[++tot]=q[1];
    q2[++tot]=q[2];
    for(int i=3;i<=cnt;i++){
        while(tot>=2&&(b[q2[tot-1]].p-b[q2[tot]].p)*(b[q[i]].a-b[q2[tot]].a)>=(b[q2[tot]].p-b[q[i]].p)*(b[q2[tot]].a-b[q2[tot-1]].a)){
            tot--;
        }
        q2[++tot]=q[i];
    }
    int sum=0;
    for(int i=1;i<=tot;i++){
        if(!vis[q2[i]]){
            sum++;
        }
    }
    printf("%d\n",sum);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Math is Simple

题意

求:
$$f_n=\sum\limits_{1<=a<b<=n\\gcd(a,b)=1\\a+b>=n} \frac{1}{ab}$$

题解

$f_n=\sum\limits_{1<=a<b<=n\\gcd(a,b)=1\\a+b>=n} \frac{1}{ab}$

$g_n=\sum\limits_{1<=a<b<=n\\gcd(a,b)=1\\a+b=n} \frac{1}{ab}=\sum\limits_{1<=a<=n/2\\gcd(a,n)=1}\frac{1}{a}\frac{1}{n-a}=\sum\limits_{1<=a<=n/2\\gcd(a,n)=1}(\frac{1}{a}+\frac{1}{n-a})*\frac{1}{n}=\frac{1}{n}\sum\limits_{1<=a<=n\\gcd(a,n)=1}\frac{1}{a}$

$f_n=f_{n-1}+\sum\limits_{1<=a<=n\\gcd(a,n)=1}\frac{1}{an}-\sum\limits_{1<=a<b<=n\\gcd(a,b)=1,a+b=n-1}\frac{1}{ab}$
$=f_{n-1}+g_n-g_{n-1}=f_{n-2}+g_n-g_{n-1}+g_{n-1}-g_{n-2}=……=g_n+f_2-g_2=g_n+\frac{1}{2}$

$g_n=\frac{1}{n}\sum\limits_{1<=a<=n\\gcd(a,n)=1}\frac{1}{a}=\frac{1}{n}\sum\limits_{1<=a<=n}\frac{1}{a}[gcd(a,n)=1]=\frac{1}{n}\sum\limits_{1<=a<=n}\frac{1}{a}\sum\limits_{d|gcd(a,n)}μ(d)=$
$\frac{1}{n}\sum\limits_{d|n}μ(d)\sum\limits_{d|a}\frac{1}{a}=\frac{1}{n}\sum\limits_{d|n}μ(d)\sum\limits_{1<=a<=n/d}\frac{1}{ad}=\frac{1}{n}\sum\limits_{d|n}μ(d)\frac{1}{d}\sum\limits_{1<=a<=n/d}\frac{1}{a}$

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e8+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int inv[N];
vector<int>v;
void work()
{
    int n;
    scanf("%d",&n);
    v.clear();
    int x=n;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            v.push_back(i);
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x!=1)v.push_back(x);
    ll ans=0;
    if(n>2){
        for(int i=0;i<(1<<v.size());i++){
            int d=1;
            int s=0;
            for(int j=0;j<v.size();j++){
                if(i&(1<<j)){
                    d*=v[j];
                    s++;
                }
            }
            ans+=1ll*((s&1)?(-1):1)*qpow(d,p-2)%p*inv[n/d]%p;
            ans=(ans%p+p)%p;
        }
    }
    //printf("%lld\n",ans);
    ans=ans*qpow(n,p-2)%p;
    printf("%lld\n",(ans+qpow(2,p-2)%p+p)%p);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inv[0]=1;
    inv[1]=1;
    for(int i=2;i<=N-4;i++){
        inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    }
    for(int i=2;i<=N-4;i++){
        inv[i]=(inv[i]+inv[i-1])%p;
    }
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.Minimum Index

题意

题解

代码


L.Mow

zyj (04:48:21) +6

题意

给你一个凸多边形。和一个圆形割草机的半径$r$,人工割草的花费是$A$元每单位面积,割草机的花费是$B$元每单位面积。并且割草机要严格在多边形内部,问你割完草的最小花费。

题解

很显然如果人工的花费小于等于机器的话就全部人工割,代价就是$A$乘上凸包面积;
如果$B>A$的话就全部用割草机,割不到的地方就用人工。
那么问题就是如何算割草机割不到的面积。我们考虑把每条边向内平移$r$的距离,这样可以形成一个半平面交,这个半平面交就是割草机圆心能移动的区域,同时还能到达的区域是「每条边向外扩展$r$的一个矩形」以及「每个点向外的一个圆弧」,其实矩形的面积之和就是内凸壳的周长乘$r$,所有圆弧面积之和刚好是一个圆的面积(多边形外角和360),那么套一个凸包和半平面交的板子就好了。
坑点

代码

367行,就放个solve函数吧

void solve(){
    int n,r,A,B;scanf("%d%d%d%d",&n,&r,&A,&B);
    Point p[220];
    rep(i,0,n-1) p[i].input();
    if((p[1]-p[0])*(p[2]-p[0])<0){
        rep(i,0,(n-1)/2) swap(p[i],p[n-i-1]);
    }
    Polygon po;po.n=0;
    rep(i,0,n-1) po.push(p[i]);
    double area=po.CalcArea();

    Line l[220];
    rep(i,0,n-2) l[i]=Line(p[i],p[i+1]);
    l[n-1]=Line(p[n-1],p[0]);
    rep(i,0,n-1) l[i].Move(1.0*r);
    HalfPlanes h;h.n=0;
    rep(i,0,n-1) h.push(HalfPlane(l[i].a,l[i].b));
    int ok=h.HalfPlaneInsert();
    if(!ok||A<=B) return (void)printf("%.12lf\n",1.0*A*area);
    if(ok){
        Polygon f;
        h.getConvex(f);
        if(f.CalcArea()==0) return (void)printf("%.12lf\n",1.0*A*area);
        double tmp=f.CalcArea()+f.CalcCircumference()*r+PI*r*r;
        printf("%.12lf\n",1.0*B*tmp+1.0*A*(area-tmp));
    }
}
Responses