1112练习赛

T2 最大公约数

1<=k<=n<=2000

 多手 玩一下啊！！！

会发现，最终的答案肯定是所有数之和的因数，所以就很好做了！

#include
#include

T3 直径

1<=n,q<=10^5,sigma(k)<=10^5

 有一个小结论！

两个联通块合并，最长链是原本两种最长链的四个端点构成！

又因为它跟子树有关，可以转化为区间问题。

所以，就可以用线段树来维护。

#include
using namespace std;
#define re register int
#define LL long long
const int N=2e5+5;
int tt, las[N], ed[N<<1], nt[N<<1], len[N<<1];
void add(int x, int y, int z){
    ed[++tt]=y;nt[tt]=las[x];las[x]=tt;len[tt]=z;
}
int fa[N],dep[N],sz[N],son[N],top[N],in[N],ou[N],label,dfn[N];
LL val[N];
void hvedge(int x, int f)
{
    fa[x]=f;dep[x]=dep[f]+1;sz[x]=1;
    for(re i=las[x];i;i=nt[i])
    {
        int v=ed[i];
        if(v==f)continue;
        val[v]=val[x]+len[i];
        hvedge(v, x);
        sz[x]+=sz[v];
        if(sz[v]>sz[son[x]])son[x]=v;
    }
}
void hvline(int x,int ance)
{
    top[x]=ance;in[x]=++label;
    dfn[label]=x;
    if(son[x])hvline(son[x],ance);
    for(re i=las[x];i;i=nt[i])
    {
        int v=ed[i];
        if(v==fa[x]||v==son[x])continue;
        hvline(v,v);
    }
    ou[x]=label;
}
int lca(int x,int y)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]x:y;
}
LL gtlen(int x,int y)
{
    if(!x||!y)return 0;
    int ca=lca(x,y);
    return val[x]+val[y]-2LL*val[ca];
}
struct node{
    int x, y; LL d;
    void init(){x=0;y=0;d=0;}
}tr[N<<2],A[N];
node operator+(node p, node q)
{
    int x=p.x,y=p.y;
    int a=q.x,b=q.y;
    node z=(p.d>q.d?p:q);
    if(!z.d)z=(p.x?p:q);
    LL len;
    len=gtlen(x,a); if(len>z.d)z=(node){x,a,len};
    len=gtlen(x,b); if(len>z.d)z=(node){x,b,len};
    len=gtlen(y,a); if(len>z.d)z=(node){y,a,len};
    len=gtlen(y,b); if(len>z.d)z=(node){y,b,len};
    return z;
}
void build(int p,int l,int r)
{
    if(l==r)
    {
        tr[p]=(node){dfn[l],dfn[l],0};
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    tr[p]=tr[p<<1]+tr[p<<1|1];
}
node ask(int p, int l, int r, int x, int y)
{
    if(x<=l&&r<=y)return tr[p];
    int mid=(l+r)>>1;
    if(x<=mid&&y<=mid)return ask(p<<1,l,mid,x,y);
    if(x>=mid+1&&y>=mid+1)return ask(p<<1|1,mid+1,r,x,y);
    return ask(p<<1,l,mid,x,y)+ask(p<<1|1,mid+1,r,x,y);
}

int n,T,fr[N],to[N],p[N],q[N];
bool cmp(int x,int y){return in[x]<in[y];}
vector<int>G[N];
void solve(int x)
{
    A[x].init();
    int nw=in[x];
    for(re v:G[x])
    {
        solve(v);
        if(nw<=in[v]-1)A[x]=A[x]+ask(1, 1, n, nw, in[v]-1);
        nw=ou[v]+1;
    }
    if(nw<=ou[x])A[x]=A[x]+ask(1,1,n,nw,ou[x]);
    G[x].clear();
}
void work(int k)
{
    sort(p+1,p+1+k,cmp);
    int h=0;
    for(re i=1;i<=k;++i)
    {
        while(h&&!(in[q[h]]<=in[p[i]]&&in[p[i]]<=ou[q[h]])) h--;
        if(h&&in[q[h]]<=in[p[i]]&&in[p[i]]<=ou[q[h]]) G[q[h]].push_back(p[i]);
        q[++h]=p[i];
    }
    solve(1);
}
signed main()
{
    scanf("%d",&n);
    for(re i=1;ii)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        fr[i]=x;to[i]=y;
        add(x,y,z);
        add(y,x,z);
    }
    hvedge(1,0);
    hvline(1,1);
    build(1,1,n);
    for(re i=1;iif(dep[to[i]]>dep[fr[i]])fr[i]=to[i];
    scanf("%d",&T);
    while(T--)
    {
        int k, id;
        LL ret=0;
        scanf("%d",&k);
        for(re i=1;i<=k;++i)
        {
            scanf("%d",&id);
            p[i]=fr[id];
        }
        p[++k]=1;
        work(k);
        for(re i=1;i<=k;++i) ret+=A[p[i]].d;
        printf("%lld\n",ret);
    }
    return 0;
}

T4 最低位

 0<=l,r<=2^31-1

这道题可以打表，“分块”打表，很好做。

当然也可以分析性质，把f的变换规律发现，可得每次[L,R]都会减少一半，很优秀

#include
#include
#include
#define re register int
#define int long long
const int mo=998244353, inv=499122177;
std::unordered_map<int,int>mp;
inline int lowbit(const int x){return x&-x;}
inline int fid1(int x){
    re ret=0;while(x)x-=lowbit(x),ret++;
    return ret;
}
inline int dfs(const int i)
{
    if(mp.count(i))return mp[i];
    int t=fid1(i);
    if(t==1)return mp[i]=2;
    if(t==0)return mp[i]=0;
    return mp[i]=(dfs(i-lowbit(i))*inv%mo+dfs(i+lowbit(i))*inv%mo+1)%mo;
}
int ans[40000]={0,522685747,277338273,76341087,785887678,507563462,561249401,292985805,806742135,348667879,761228614,186115155,535821676,816237962,927999445,210807679,852451049,496982772,494054984,725742036,275314565,821973791,873464609,855176710,490966226,141516364,720840205,141802434,208538019,901608253,104062712,420195557,951868877,60487854,419137602,537580626,793829194,758616944,306504129,881495657,311730820,806377553,599739544,536091719,262674811,892018762,174468645,947453780,413255326,417987292,390053235,90644589,543044691,483420298,353585759,209584813,780103873,624369078,339088275,473175316,903817131,245350587,536100516,634805983,168460180,819523537,496425335,235608501,280447262,431830064,739667598,49870050,413133261,166666106,152773736,56946961,485272668,216252138,963517307,928118111,404563330,286603268,816770027,437858415,176271050,143978997,177899448,758765495,61339568,127208377,835193308,191219458,832541221,348308796,861907344,233968177,281833526,14967163,280467905,753621794,912126977,81849251,665058852,707045610,213453663,911316639,621297213,857639103,804152409,178888502,589801444,401442992,952991228,760886837,746367702,637088184,241292672,416538095,868374962,910696037,536837263,798425439,223506783,486263444,798910434,277111725,246522759,864194456,630131492,102923511,801263564,57385496,403055944,874214678,855703285,858881532,37066582,223109195,158100545,37829940,180597189,158817127,551266871,889705777,685985748,447703344,622412406,756395968,974576026,624379864,346222388,397791292,880809746,82260439,361909045,75521370,168316254,165433765,835212590,224057937,630228350,671296711,743784970,482045836,878554975,862734113,423019759,760967157,369578415,704959405,471614701,301701936,502759259,400862996,395556671,676480191,700913435,869282163,183978644,292358642,766542400,507814533,518023925,956732641,198197667,82974902,462067705,976552778,737814472,36413576,860071731,436621711,66989926,941336777,150234520,809150974,54429131,459451398,87355188,993875748,9785755,355938939,350813560,35792814,866643025,269529358,701694645,919884390,604515960,162016835,139972430,289500720,950051043,400505142,58571582,697878731,761041356,774196981,610766046,296003335,406990353,394669253,655508417,594453568,356521585,642185537,570830843,383491633,49120597,65234459,285548464,49696353,103701466,341109831,269770319,226573527,719529901,347181146,31874826,770762401,861121880,691347781,3056110,874973314,240819175,826093305,460850376,219413211,388285917,344112518,622694635,717994486,531200664,559151334,26154224,356564144,619229763,881573521,234827040,973111514,829743618,305151415,511351378,504559831,282317162,546756095,267794108,69841334,166404147,750954372,310218894,350248374,616549575,413129311,924041524,322286153,677885860,150785767,173318798,149183,130700724,305327821,532743164,450766666,626816160,411422301,58201815,427585093,305446369,945862549,666563421,310050085,608660653,590257610,214064260,758798271,695691900,61966863,681133629,734245730,1528889,283298684,462719535,144855524,749639549,970718459,638622380,596199602,730222859,753257300,76064761,321961491,652402854,44892055,354459479,447389791,728401548,500093865,376511479,641499877,163314037,154057841,834847210,61908896,740904021,624175159,157542972,720973083,85880518,919500191,259042477,26289545,476342447,310627414,529973791,231190169,840193145,479209454,34368774,817107162,213641756,291396735,23367733,613325457,240234528,131392137,529094309,551782592,754383376,867544461,717205282,93053604,71572463,652745924,120055665,370541064,386519178,312786311,663197976,52033826,719240584,74975423,468021094,826847485,264388506,294840811,767902150,931949179,19754912,485116015,12244858,705272023,782585523,445241477,709611783,756532686,583628728,235199574,864770158,813462630,210790133,439327242,187012066,952174476,731547079,251828183,863234431,251915249,517769234,571077304,171132880,37802084,698595936,996797398,791449290,758395079,850310682,51125119,275286381,549796185,301592017,780777779,65515524,645738974,989742178,131546794,752393946,491258347,373567018,697874596,681988786,647252105,793992715,977250510,234866679,844841344,492396201,244062475,618221003,708585023,698772718,587310517,190050556,200209669,715314350,187133749,555462817,958534504,563925246,97859024,355885794,421749716,782819250,972599792,130168782,398284555,585276781,108440337,31775146,453733933,151368171,891693,79271550,376849754,276394914,317655400,130333771,866601199,273826652,879360042,889564326,223067833,303718855,46244490,996119072,873352015,765115093,604131887,473816011,158553681,695713377,450595541,846313392,779090255,942763407,191996753,657549907,326623897,93234767,964601263,177956444,275458844,539839779,602759804,338828441,683469714,389721110,826364145,250249054,41824615,631446761,590633193,548811870,57957497,529806158,562147340,182967568,61950307,397443959,220643692,236459253,41053957,533024240,206652748,421767795,282581949,689281236,765719080,143337473,874405567,440616102,563192864,960412569,457171179,228312121,146929495,32724496,260402550,473562466,482669067,52657949,316866892,725426305,755897589,281974486,246944883,627634098,199696719,447424993,586128581,18459373,841642231,494225619,660967593,552038789,870887004,130526475,813475125,172839598,659687313,669912019,853096014,186197321,544401467,314058298,42329643,918294577,406005228,419010427,788281171,346137971,689657052,953704100,840765949,913271208,296969432,751186233,844188500,466417476,762974059,603909329,280446807,857212137,900937550,743664274,778907832,583296514,867250059,763421062,973327353,170907794,198576868,155980262,328429130,423350885,504285405,598584227,882460971,919914738,357075715,864474126,240779712,534682597,656595314,168569536,760546632,686611964,293645479,303580771,282348526,251039222,294185125,907891209,313274919,727157147,639732506,774374742,678155495,274645197,551062119,36290435,746853378,285923648,12097527,33545641,844421110,943641159,286918280,530541906,621242630,460386244,989462323,476423179,884028283,743576021,990566430,109377071,450364826,639299155,483200790,934778688,843837462,906101909,441589363,919066898,624132473,622606134,447003748,927274554,511045078,232151543,387028777,656541661,770897892,778331701,608504503,346080843,915481865,889510907,774907096,383730364,681934828,672779464,50142157,463606196,29181379,840418563,422089510,51298608,487073277,387729764,690017335,368122733,505861048,324703855,399798376,194232431,353202907,897142123,586204574,567983808,631641388,669781597,455988172,579957421,151539070,661020310,495405794,802769304,106471447,214903558,869443346,751048465,994486798,748987823,416238711,322032334,669327068,234987059,216657060,803560954,822389308,951178252,974550384,199614302,331720013,858676218,331476529,350391561,298379307,865940219,170358228,674890921,225991108,635943680,80276036,262529440,205988608,885429419,239136816,876186150,657981418,958556935,209033893,131481829,632746654,647792433,501869629,864418643,86001961,973655464,653412439,813060823,206573777,985379225,397025094,118255561,372119908,795091375,783228338,390499942,598758014,969600246,474740248,483705336,315023250,585632291,393629942,483338819,502304472,804636952,885293274,461377105,604124605,569434216,901061672,74257247,609265836,937362021,1937308,23071312,505851908,573241168,612956124,584527877,862863542,845113755,55595397,690817922,588962018,55784770,865773823,239239540,592689015,611376806,592474929,143079620,101272352,362729793,889582861,821877962,322493035,463257240,121136465,191262415,43031503,713994616,355462951,654689057,147085092,100471290,970825500,186635997,828628033,877037129,140376888,219350997,780081900,256172679,138112257,31653344,523943910,900029739,659357775,86546856,893223773,448594309,603479535,668042602,674625846,88341045,61815037,67928695,487292967,186440840,478863878,703737485,788960321,654200721,895004979,4981987,572932225,577732964,432432103,583277321,294601837,35352000,277729028,392236273,296674339,86960188,111304435,608265816,273539651,683913047,710756826,191536262,172234127,473110708,46213694,856957292,310804748,392107504,720924879,973763769,21227820,589659357,320661303,82016886,636584814,713663289,524919756,851805581,661935618,186344502,438510122,1899297,210674487,70075610,839152933,229797457,382717270,476156683,219757823,393978292,779985259,741384986,294469900,715715304,867470103,29884588,377537219,9225600,627721637,202150228,341206469,766022061,290975969,457840964,787100590,677646873,270141199,80133814,123163459,730240266,406076768,790388221,487418278,420415271,182819500,885144273,939957763,295248186,406093201,44130685,599549383,183109629,804481118,57356737,654041638,594311488,349481154,752298251,368228252,72749641,126232912,720563121,721274627,851228652,186031198,858368160,691385613,953372634,703543104,667720497,725119383,686697630,711373726,738412261,888668981,481771494,771075067,423338530,943857311,70860510,857106995,332436786,263304339,606044097,573376460,611077551,643279807,236491212,222452006,993739232,857108964,146228028,91884451,451885244,343585448,107127664,371324318,428615379,472183165,586576604,983128815,521734762,943128116,989450317,570950703,747798850,204518542,753438720,463405676,674058764,427246950,331381215,767436147,856398583,401780638,193590288,527005854,525185706,470514686,435453004,572650983,972408016,266851697,462729636,787372027,315722278,439711430,534986579,12288847,416459535,200151883,389228142,740562385,559123031,968106259,122024566,321158736,345169325,436512423,243510927,444130751,446466713,453799427,624079641,165548271,412096523,596516089,993703672,186621907,504740048,867235651,764883574,350084247,827061901,700558718,284248950,463772254,40200429,882144481,518607778,34771600,954693527,665279834,235531342,244053868,300435502,165515526,876116894,131952677,923371968,802809282,696384966,344695887,75232610,87574486,461477509,8308327,541027521,208643975,344693110,910953272,989031736,825005418,854731200,777414277,326459036,368750833,774273054,855087678,698004382,786820947,772855249,503077764,872779388,860544617,175424885,978774907,231115173,561727573,769539631,125090922,624134597,325841608,993880148,986999106,698089912,101708592,22274130,251705493,195575036,887633089,655886048,989804295,338020769,642205749,319888088,354978876,673003861,911033544,40156684,528085739,653296304,544994790,617960693,171277059,652379589,217183053,721978804,710327435,135129674,200200258,905273812,444506653,895413611,879260229,448535157,126141903,643704116,285051513,969595364,150943374,217884470,592302259,594558489,461567967,182979514,937586249,382386381,433807948,289003747,229711716,543696485,504107897,71247873,877865156,433878146,240661702,693586731,985375297,257915516,463451428,24122537,449419261,174001770,256606825,687976125,473394908,624039839,380230912,435126846,280089098,583753345,981412792,780470121,463493392,636536923,512567654,702055724,292802236,232704690,349879603,823413733,804512373,969880195,889289293,443911328,498535549,539303806,881227197,493620338,714409461,544820237,374187975,209932582,151573138,775297187,674974721,683007593,407946240,817097130,175108819,572476114,166299941,7209831,312675158,531321934,388244624,292352418,900839886,138285144,517945122,609758223,902625224,486566327,385752959,42062102,927032631,178974996,849376174,978465557,160582208,791867541,983575498,88996776,870051109,59089070,289620456,577800468,817959063,775399808,564849323,215896504,39639943,935782775,892638900,318026790,277395603,738698801,335156085,561001767,489296488,306261568,166406317,351883063,110888076,708235177,229443277,703256167,979912451,398084751,801446141,239814191,986953771,257905782,432086064,876048981,790432074,437364653,862509770,557409969,714201088,689807071,482077966,313248338,933418412,882763469,784361835,946629899,993511759,760631497,189649939,903890680,862049930,273703197,914986521,130692982,624660841,768411866,961359880,788980190,20474986,422134258,176789172,761487068,523341797,679856601,632507875,276509110,961858538,165427816,646689701,759236425,305923925,609044640,761583653,795445961,289659948,341420165,16871174,522461171,361500197,722618367,518452349,193853340,470102787,169654793,471497082,639336654,36152977,748816614,920891665,52849018,448448321,873557137,919458484,662972985,37376529,715372684,374126071,186768704,799547233,586064709,630542808,174671830,362183758,854325107,748383275,439215631,198735808,638457648,726197567,524979702,10133962,343945042,557159436,311790735,783552969,263214066,662481194,604099492,706479092,277125057,194827612,87121076,707540080,571411510,881974403,431265934,816825789,877535296,170924306,763850052,412766962,707630858,33726147,716437921,27289948,89744025,385583112,979317338,253901157,188140423,615259744,955531721,278546273,158316865,547470248,497975438,424410541,119008164,125689245,717660514,377214168,624661498,41405451,885113365,869144186,781879501,650538,800867982,667001542,535373974,843558975,996911333,852541100,780601106,742336827,462203474,53296649,23770141,558137620,873818982,81546978,624926097,503093393,586430780,455715801,142811188,381846651,773172885,680318815,898307530,565653949,287366929,593051694,456625720,950440100,302224536,729634122,535077599,903662021,570693218,483683862,628034222,200498710,336102983,466744203,677842174,266955810,739148195,594171802,977257948,166848121,528909639,262322574,286813818,619016552,258670471,636741773,510904113,475682076,706362956,557445081,975668351,148917087,242020785,30836922,848802400,142438973,933913507,172930379,754204712,638674915,934840386,808549049,514048439,581155511,143166461,441854144,784634940,954397239,107833351,402872806,206606868,583835353,512423345,442046222,902181759,61393880,658528339,546519491,523330495,928670753,605175101,263610756,714285470,461334158,238441114,527273494,166993481,125689657,76603514,160142594,636124656,978473566,661705046,773737682,782610547,207587771,580398399,691153808,208922654,392332658,733672321,515685652,838311475,40314926,610483910,692964812,607586555,900633377,434433317,14053987,170259690,350776489,495398825,665681034,400519188,270849511,250471855,939318170,502674089,855633536,504433812,738227423,785417698,922568571,550966520,347655040,495273676,192697959,638436342,657561730,184299033,528802283,393667315,940092951,788500921,979062574,281599492,406499649,706704452,246005743,428490642,948579095,337185335,10416569,7946463,76254296,596936116,351016302,149466128,872822887,136016107,848857241,80898287,593863898,928565477,824471867,859578242,187288121,650820345,605291694,27729517,899928951,842776667,817811771,535360390,681958937,549919204,643248273,402474944,982153154,256685273,415408269,802578814,268939470,867342735,26145417,892973224,978639228,472977383,962445795,144627635,755120369,512864594,616122638,19809957,882343748,676418927,175635954,171273168,11556224,640959372,729780692,1000190,237571841,910000259,350566019,268090839,732525400,42965813,790903989,858812649,106684300,329324161,326581295,128333920,748066675,598514264,841149034,973189736,191484051,480388097,126524977,55169982,832729854,790443532,34693382,712400487,68685356,716141911,479073613,578883419,946203959,259833604,430086060,183783108,232454035,62253507,791805399,84745991,294417941,642598549,39929083,432376241,14235254,134948392,509551679,136218258,544678390,687668232,129154702,566259384,396682705,974548019,119300575,793957115,468431464,361376002,349824088,302531382,868621070,142810070,84228799,340191276,348098250,698244459,253903436,431401643,520187920,252728845,375338644,761340690,955909419,312757375,201959659,536792379,371370744,519181917,808021537,290621160,810799456,552375001,494895484,377938048,2004349,510617659,599479163,161623375,133673081,773703583,793590674,292472430,508283936,889644509,658058361,378377252,411798498,428577528,696702023,133259403,279045828,48093019,420611559,608456113,203394361,951727591,731258104,263935418,578096106,476116449,211684100,480858770,917033863,57696530,519797775,617096652,791274917,664241890,987406700,83894661,359896227,326219387,102104760,529787725,665745131,684375191,509529217,351602012,636631149,842092121,284677795,252321056,642488282,716289582,521870470,166219937,12578111,77534620,181507933,821267340,35682560,349285907,868084515,781700590,354461597,431599682,318696662,920010985,414327659,257545819,552129769,240152508,641239911,188767942,266305751,460955231,831824831,673668180,818834149,173971537,987087225,381292429,352922795,839184200,554358142,460685577,275498007,570461063,127928434,154493472,215855531,312845063,401379747,412954036,481833733,946659666,937971520,859677647,405487243,125752264,405243783,112565573,780395497,996895558,121717767,407468599,98111290,806678191,798393562,150731513,728738412,806984764,630886903,110352681,955976310,336517145,550146450,272300119,255125228,56225122,50292872,648349572,575817487,514060456,115086101,324158139,445191428,384546407,908487623,366894192,426773779,609668421,558812297,87184415,815185104,353885966,639486046,553720161,198446796,796254974,743291016,700651790,504840292,669019965,181891895,673069818,140528517,205010990,483689102,496283412,817873586,385960192,551351021,377172525,474936106,512435955,400328052,473245126,385137731,24134102,267839492,995242261,328185645,621927880,395083315,35373656,277520206,154689083,745523237,345732647,262357448,231078290,616862681,423121001,269360958,583022353,766831751,524096838,688485964,96108387,964329870,438368249,703622916,115988545,846576962,539650365,239307520,510455196,204310683,88729384,690296002,628395721,538729961,715879432,355615807,432459869,834247783,304601457,929119220,485148344,205855925,290129685,737966048,18299357,918413126,751149029,232094407,600678368,845032622,109958249,971569903,820995077,165156233,256759329,816314053,383716773,193989595,457103695,60819840,518215331,628618534,922867838,435018906,430931713,731141336,897657054,404975507,870793337,901902513,508412207,176277565,381663455,514951558,504104001,426907178,53394683,229977069,714337970,393884546,678813057,117108341,829291280,259886629,706601010,748154989,799195104,612208270,641670392,142359215,815661941,30535939,18780310,851235261,27923315,92845167,66802072,933282727,211615951,894027881,808578028,15186897,10221685,454914703,805066405,857832989,77327911,618655983,245203781,707630997,115510530,404075070,742767314,946881569,313725443,739875606,863481511,594963283,821880725,26624819,372931737,597134936,791549508,346414685,55759970,125149365,897207488,481431122,326001618,689073803,149424582,253301120,896371711,46306038,661777358,961615466,280654549,828750101,726457304,843450309,194259754,224892820,121866865,675588246,390977363,515940163,204021455,471110136,954238270,836967031,926230735,531552488,761212841,14252854,63009593,3569846,651806319,884733463,526797696,377311672,933638768,602460856,641699047,402269064,583884757,396802898,435164818,211251922,523742414,481859165,475467858,21009388,27878399,280511113,472378623,206728001,698718185,174592411,732065755,32353642,587654789,180700287,553048844,646256204,90689826,605038904,318657678,610701965,666415096,381807026,271100987,82765908,178438398,474261825,453396047,626704740,529535680,687939480,284355924,465420027,235827362,533085228,898596404,204825112,84765807,598326285,665247022,836626414,165610183,476259580,907329034,269937480,12924610,992184453,213452170,271162899,368716081,408777667,240666151,398821450,219505636,145426828,920678367,835874021,492432577,682761014,560703957,14229995,510914914,381641776,754306642,877506806,688200724,901883887,918388000,294336594,178473815,89337310,42509709,140026846,757970403,25852790,199578718,960910962,804126890,60422,172360696,395836268,653918418,700580157,874406593,405718304,333534319,642059541,316024276,3046082,367653567,405611483,740520091,453983786,493929038,339842653,997885523,696446203,708114556,745142480,183687203,857450351,634976558,300021092,316138113,31394131,264994802,903053114,598144904,987045658,676289689,242711162,699189081,63786725,515056256,133246722,675188008,178687932,700992888,524147665,908979036,234045156,600355985,478864016,669225216,729744439,26101848,649465382,737415665,296309727,135043065,302947712,135652174,947233038,215495852,47550795,298325087,380167363,258506454,841683963,435034506,309586262,195640399,880061023,528813604,525623069,551609791,329436156,502465132,404062191,847298203,125664158,942332959,627453716,43584227,842168816,646116851,655942504,362943512,961647197,968862966,483930642,664446177,115058508,964113335,630659793,495449083,647008280,980774498,934794921,200909129,523272197,281499034,832134759,328379229,823810268,238076614,560777107,304246882,595066911,584794573,473763021,174971286,578094314,202380564,283929396,731755920,182587756,443731315,83833733,237871889,735534282,5407597,707769779,22126505,310539645,937182137,646543528,536708535,796148960,918641897,903505920,5065867,171010634,109674549,596488289,154395576,744785303,128831463,376362259,26654059,417440586,199570692,358266012,723124702,958119297,810591489,688179718,381458854,415494208,835974214,102854631,722544878,106751222,993300841,313395140,134904995,934659951,737358857,900164806,768112084,56961418,970211468,669238342,916503482,116373833,28372246,551282233,929238856,654227625,77042168,162097612,310284303,366267603,119627023,102648903,336829314,327283445,753730799,219523765,76271077,617993155,780171039,165551178,17052344,377860335};
int b[40000], cnt;
signed main()
{
    int l, r, ret=0;
    scanf("%I64d%I64d",&l,&r);
    if(r<=1000000||l==r)
    {
        for(re i=l;i<=r;++i)(ret+=dfs(i))%=mo;
        printf("%I64d\n",ret);
        return 0;
    }
    ret=0;
    int lim=(1LL<<31)-1;
    for(re i=1000000;i<=lim;i+=1000000)b[++cnt]=i;
    int x=std::lower_bound(b+1,b+1+cnt,l)-b;
    int y=std::upper_bound(b+1,b+1+cnt,r)-b-1;
    if(y>=x)
    {
        ret=(ans[y]-ans[x]+mo)%mo;
        for(re i=l,bur=b[x];i<=bur;++i)(ret+=dfs(i))%=mo;
        for(re i=b[y]+1;i<=r;++i)(ret+=dfs(i))%=mo;
        printf("%I64d\n",ret);
    }
    else
    {
        for(re i=l;i<=r;++i)(ret+=dfs(i))%=mo;
        printf("%I64d\n",ret);
    }
    return 0;
}

#include
#include