NowCode - 5678H 中位数

H提供一种打表的思路吧(本以为是正解)

如果我们将表 全部求出来，肯定是无法提交的，
因为每一个的计算都是独立的，因此我们可以考虑分段打表

考虑对于每个数，存一个值
题目大小为 ,因此我们每隔个数记录一个，存入数组 中
也就是

这样对于询问，答案就等于
后面部分不会超过
时间复杂度为

ll n,d[N];
ll a[]={0,74647,265660,562004,954089,1445792,2024949,2706101,3455881,4310392,5263989,6279406,7373523,8587425,9879310,11213980,12684045,14177771,15806472,17460121,19244219,21080191,23034187,25044251,27163813,29296970,31538778,33906002,36276593,38738931,41241992,43898091,46537477,49451036,52349848,55283747,58235239,61429585,64539187,67721107,71065685,74336377,77936056,81611183,85083579,88847624,92506043,96255418,100285630,104187622,108339209,112384030,116695007,120958679,125347845,129680221,134234707,138898064,143568307,148283371,153101887,157909113,162750448,167705550,172804146,177778233,183285323,188386169,194067715,199208869,204487995,210298666,216091524,221856625,227512363,233417195,239410466,245120982,251479294,257483489,263779615,270057648,276416169,282875494,289356178,296032777,302606538,309182848,316197659,322552913,329732499,336762778,343614896,351190996,358309748,365454688,373178358,380493104,387783140,395383306,403013650,410525031,418507782,426348486,434013169,442052346,449983337,458258478,466051964,474461193,482809357,491045608,499502427,507776940,516614736,525005442,534031468,542766617,551716711,560422992,569440916,578556970,587622795,596849584,606332098,615540669,624883261,634272690,643870432,653725314,663159769,672894244,682757788,692631614,702397272,712308155,722723865,733262466,743146135,753629623,763592132,774205607,784944967,795541147,805811981,816001825,826876607,837549233,848441357,859272594,870855578,882033536,893681614,904966526,915551383,927203852,938981318,949802763,961483099,972639339,984478385,996374739,8326988,19875330,32025732,43753819,55346845,67512031,79647711,91322135,103954459,116700440,129076921,142154210,154236093,166889278,179259959,192654593,204681430,218242636,232389134,244544424,257260441,271230682,283869264,297581897,311845952,325175632,338966840,352104681,366218547,379765707,393487997,407869579,421793365,434754504,449226128,462804690,477606097,491969146,505998560,519867948,534686333,549040964,563491939,577644790,592284332,606965268,622234096,637322325,653032570,668470879,683953621,697979277,713414381,728902283,743518154,758358305,773759213,789857511,806304676,821270914,837047839,852762961,868600000,884797685,900818287,916759787,932751706,949549468,966454607,983082107,999426079,15523814,30985118,48046833,64032099,80218873,95887485,113277722,130337154,146943791,165326165,182214208,***989,216968947,234264354,252249423,269675099,287806422,305183539,321778430,340213442,357861590,375493841,392737922,411558576,428775144,446622303,465588215,483098989,501021877,518257589,536776193,555727237,573793073,592121179,611576445,631970953,650463847,668675613,688481538,707185417,726923654,745074426,764106142,783293992,803220594,821828948,841353653,860178054,880768419,901111190,920236128,939346904,960304334,980410879,998538597,17574529,37201830,57612666,78521143,98479183,118468364,137194433,158297963,178186041,199280638,219028353,239436674,259950508,281554793,302897379,322710454,344886368,367000863,388654714,410055694,430047474,450988784,472399889,493936368,513925091,536358882,558658038,580542990,601447788,623646200,646281128,668607175,691901334,713989713,736221750,757978403,779536555,802620988,826163770,848109224,871789535,893873207,916223828,938591822,961790451,983355100,6714763,29833658,52150211,75964211,98994956,121772155,143974266,168105182,191289974,214331340,238066649,261924971,285553661,308764263,333605088,357092174,381245253,404476931,428773868,453771710,477978444,503317876,526904787,549693021,574856232,600325584,624677618,647641691,671279071,695384427,721359151,746563569,771334357,797446162,822314024,846111092,869591617,893734887,919715865,945620178,969683022,996382735,23043324,48470348,72975003,99005550,125758424,149587172,175675587,200796167,227455552,253472514,280710224,306796108,331819962,357069470,384090269,411599586,438590691,465640235,494139967,520253454,546486888,572965348,599274009,627077983,654894758,680251611,705717316,732376967,759568460,785211950,813846791,839800015,867513892,895463509,923985599,951345376,979051939,7152610,32480265,63129913,91903208,118601782,146813113,176987069,204996988,233452222,260902838,289477211,319290039,347500064,375531274,403277418,431874361,459665278,490427055,518735695,548145477,577780351,607119139,638061908,667784049,696110793,724960503,754010589,783924296,812777565,841474806,872704738,904598995,935330101,963372976,992059712,20927573,50085568,80813577,114260411,144480703,171858716,200659664,230866218,262386636,292175297,323457879,353680405,382757620,414349726,443123276,473327726,504459046,537169641,567702741,596690496,628814586,661543419,692115872,724965177,757444278,787610459,819111593,850767887,884513341,916429172,945896452,979306729,10847549,42598107,74736161,108633387,141419395,170720031,199934765,233020861,265331455,300196833,333236818,365558572,398747030,428854177,463983528,496910683,532696411,564194600,598299890,630041797,664513284,697660657,730360256,762251148,795283821,828614923,863295961,895568725,928965069,962139118,995651303,29639085,65194982,97489872,130986946,166177947,197464669,234086451,270765056,304280351,338971144,371851601,408668410,443513488,475991061,510456251,545535605,582278479,616799197,649899616,686024598,722165229,754925594,790853330,826109735,860674448,896201416,933069960,967286101,3627616,37804220,73320351,109679168,145523993,182208176,216417358,250900725,285742076,322071113,358138171,394935906,431857701,467843595,503506947,541264268,577883019,610353729,649418942,685347742,721172834,758231952,797082261,831926529,870220262,906001098,943185005,980742552,16467798,52559915,89720232,129017242,168296570,205258260,244305250,280395924,316648664,353897946,391945778,430334951,469821562,507354191,545090587,584818991,622062507,659979270,697579609,737383269,775971334,816966950,855593123,892006553,928981390,965173381,4703419,45218901,84112834,123717802,163694450,200793723,239366268,278044843,317897520,356523466,397987849,437928019,475595994,515982997,555382834,595992860,636978780,678397514,718356850,756933587,796944518,838597348,877193286,915888358,959440598,808713,40033858,78949329,119302617,158852221,199139444,238944497,281220953,320493523,359523348,399748867,440386520,481299174,519999342,562766332,604625705,644898891,688595179,731199007,771496230,812475114,850620491,891684508,934452102,974180262,14698530,54810631,99800748,141492947,182788578,226021487,267450693,312846633,351334895,394221647,438872297,479829253,523420248,566072820,607444757,648442066,692218236,735342458,780348900,821299097,864213035,909053440,952127345,995008473,38853025,81543378,121960575,165776351,208885177,252305436,295794303,341077532,383715605,427914244,472390446,511859100,557458544,603699014,647535354,693569455,735440953,780339833,824176459,867838069,912323597,959363337,4602611,50745352,90040947,136723174,183607940,226540353,272767050,318187113,362654890,409089257,450422184,494510234,537985090,582352571,630784872,675147332,726615733,768931923,816841704,862005211,909765351,956215407,2900959,49416272,92580047,137662374,180923114,231077350,275305399,319640100,364008082,409393322,456036269,502659753,548016419,598494848,646295921,690470469,737578355,786134566,833572250,880859343,926668821,973708696,20331586,68739452,115759539,164810582,210347658,258340377,304451109,352760639,398291807,443811546,492717481,537870437,583057767,628973355,678197928,723812654,773420850,821256688,867814219,918620543,965769096,14719587,66143151,112577109,157972820,205032209,256268460,305693116,355425653,405684081,452547362,502657964,550211542,602990286,653650351,701610614,752377870,800848739,851244363,901661584,949758067,999766495,47823521,94976355,143965645,192940167,245366007,294701165,344053934,396779501,444882541,495406105,547219906,597668902,647725866,698837348,750239505,799119536,851696037,900898986,954458718,3659193,53722935,106061133,159300034,209146057,260073287,310337121,366127298,412581569,462720970,512677090,564598183,617092419,666787815,717612640,767887435,818601720,872999256,925133362,973706425,25169174,77751810,129184537,181992960,234925408,282786573,339782566,391905442,442745912,499572037,552824423,606660727,660672656,713991306,764277720,816388111,868702878,922159565,978596304,34410110,83753142,134009459,188328411,240984048,291254933,347244587,398363867,450734338,502168299,560357588,610399132,666642335,719496774,773044353,827641237,882668582,934296586,987049588,41991014,95024338,147474620,201774467,255946794,311348965,366575242,418290107,474088594,527222117,584854050,642516907,691645693,750223621,807624046,861077402,918549023,976668757,32855381,90600675,140923449,196899421,248701865,304514280,361804947,416922790,470016259,526952712,584927365,642348925,696539231,752785641,808068279,863519168,921472591,979727233,35677632,93567699,147834873,201825229,260249308,314757591,369931495,427409204,485286670,537475917,594858421,654064427,706041824,765238567,823797463,879447536,933097271,991636688,46493490,105175011,164186633,224513096,286127589,341697289,402292450,457465744,508708688,568170295,623859014,680923830,742590243,801328774,856719916,914905709,973503906,30892301,90327140,149478134,211505044,269460729,325055217,383346774,446040027,503209179,559369929,618504892,673982629,735728679,793438470,853071437,912296964,970542872,27935503,89228482,151668815,210145844,272751885,331581819,386229430,445973657,503068620,560828372,622453104,683793280,744555777,807115360,863947423,922382577,983908274,38117330,98451035,161704024,219374316,279929952,346496691,406349991,467610981,529274800,590238315,650903807,709854239,771486877,829433663,891533657,951625648,13822262,71146235,138771423,199521424,259190089,316483822,381104913,439662088,497984136,560690924,622169427,683738815,743369561,805366694,870659759,928805696,989628937,52286538,115179241,182179506,241200910,299513340,365733807,427509725,486381445,553525414,617468647,677045223};
ll gao(ll x)
{
    ll now = 0;
    for(ll i=1;i*i<=x;i++)
        if(x % i == 0) now = (i + (x/i))/2;
    return now;
}
int main()
{
//    PLN(gao(2));
    ll n;RLL(n);
    ll num =1000;
    while(n--)
    {
        ll x;RLL(x);
        ll b = x / num * num;
        ll ans = a[x/num];
        FOR(i,b+1,x)
            ans = ans + gao(i) % mod;
        PLN(ans);
    }
    return 0;
}