190428 Spring Training 2

比赛链接

题目	A	B	C	D	E	F	G
通过	√	√	√	√		√	√
补题					√

A - 搭积木

题解

二分答案，然后贪心给倍数为 \(6\) 的高度尽可能安排人来判断即可。

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;

bool Check(int x){
    int a=max((n-x/2+x/6),0),b=max((m-x/3+x/6),0);
    return a+b<=x/6;
}

int BSearch(int L=1,int R=INF){
    while(L<R){
        int M=(L+R)/2;
        if(Check(M))R=M;
        else L=M+1;
    }
    return L;
}

int main(){
    scanf("%d%d",&n,&m);
    printf("%d",BSearch());

    return 0;
}

B - 线性迭代函数

题解

式子可化为 \(A^nx+B \sum_{i=0}^n A^i\)，用快速幂 + 求逆计算即可。注意特判 \(A=1\) 的情况。

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int MOD=1000000007;

ll QPow(ll bas,ll t){
    ll ret=1; bas%=MOD;
    for(;t;t>>=1,bas=bas*bas%MOD)
        if(t&1LL)ret=ret*bas%MOD;
    return ret;
}

ll Inv(ll x){
    return QPow(x,MOD-2);
}

int main(){
    ll a,b,n,x,ans;
    scanf("%lld%lld%lld%lld",&a,&b,&n,&x);
    if(a==1)ans=x%MOD+n%MOD*b%MOD;
    else ans=QPow(a,n)*x%MOD+b*(QPow(a,n)-1)%MOD*Inv(a-1)%MOD;
    printf("%lld",(ans%MOD+MOD)%MOD);

    return 0;
}

C - 简单求和

题解

对位置 \(i\)，向左右扩展 \([l,r]\) 使得 \(a_l\) 与 \(a_r\) 为距离 \(i\) 最近的 \(a_i\) 因子，则答案贡献为 \((i-l)\times (r-i)\)。每一个数的因子个数是 \(\log\) 级别的，因此时间复杂度为 \(\mathcal{O}(n\log \max{a})\)。

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

typedef long long ll;
const int N=1000000+5,M=10000+5,MOD=1000000007;

vector<int> fac[M];
int a[N],n;
int cur[M],l[N],r[N];

void Init(){
    int sum=0,maxS=0;
    for(int i=1;i<M;i++){
        for(int j=i;j<M;j+=i)
            fac[j].push_back(i);
        sum+=fac[i].size();
        maxS=max(maxS,(int)fac[i].size());
    }
}

int main(){
    Init();
    
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        
        memset(cur,0,sizeof(cur));
        for(int i=1;i<=n;i++){
            int v=a[i]; l[i]=0;
            for(int j=0;j<fac[v].size();j++)
                l[i]=max(l[i],cur[fac[v][j]]);
            cur[v]=i;
        }
        
        memset(cur,0x3f,sizeof(cur));
        for(int i=n;i>=1;i--){
            int v=a[i]; r[i]=n+1;
            for(int j=0;j<fac[v].size();j++)
                r[i]=min(r[i],cur[fac[v][j]]);
            cur[v]=i;
        }

        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+1LL*(i-l[i])*(r[i]-i))%MOD;
        
        printf("%lld\n",ans);
    }
    
    return 0;
}

D - 构造？

题解

考虑 \(p=p_1^{t_1}p_2^{t_2}\dots p_n^{t_n}\)，不妨假设答案序列为 \(\dfrac ya+\dfrac xb = \dfrac {n-1}n\)，即 \(ax+by=n-1\)，且 \(a,b\) 为 \(p\) 的因子。当 \(n<2\) 时，显然这样的序列不存在；当 \(n\ge2\) 时，可以证明上述式子一定有正整数解 \((x,y)\)，简单证明如下：

显然 \(a,b\) 互质，因而 \(ax+by=n-1\) 必有解。\(ax+by\) 在 \((x,y)\) 取正整数时所不能表示出的最大的数为 \(ab-a-b<ab\leq n-1\)，因此 \(ax+by=n-1\) 必有正整数解。

剩下的就是 ExGCD 解决。

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;
const int N=44721+5;
bool notPri[N]; int pri[N];

void Init(){
    for(int i=2;i<N;i++){
        if(!notPri[i])pri[++pri[0]]=i;
        for(int j=1;j<=pri[0]&&i*pri[j]<N;j++){
            notPri[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

void ExGCD(ll a,ll b,ll &x,ll &y){
    if(!b)x=1,y=0;
    else ExGCD(b,a%b,y,x),y-=x*(a/b);
}

int main(){
    Init();

    int n; cin>>n;
    vector<int> fac;

    int x=n;
    for(int i=1;i<=pri[0]&&pri[i]*pri[i]<=x;i++){
        if(x%pri[i]==0){
            fac.push_back(pri[i]);
            while(x%pri[i]==0)x/=pri[i];
        }
    }
    if(x>1)fac.push_back(x);
    
    if(fac.size()<2)cout<<"NO";
    else{
        cout<<"YES\n2\n";
        ll a=fac[0],b=fac[1],x,y;
        ExGCD(a,b,x,y);
        x*=n-1,y*=n-1;

        if(y<=0){
            ll t=-y/a;
            x-=t*b; y+=a*t;
            while(y<=0)x-=b,y+=a;
        }
        if(x<=0){
            ll t=-x/b;
            x+=t*b; y-=a*t;
            while(x<=0)x+=b,y-=a;
        }

        cout<<x<<' '<<n/a<<endl;
        cout<<y<<' '<<n/b<<endl;
    }

    return 0;
}

F - 数位和

题解

~~分块打表大法好~~

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstring>
using namespace std;

const int N=400000;
const int a[]={0,43691,79494,117251,154754,186561,226142,259122,293749,328266,357923,394196,424906,456936,489122,516988,550627,579519,609471,639669,666027,697359,724669,752685,781082,806095,847505,881829,917958,953748,984457,1022151,1053894,1087182,1120224,1148898,1183663,1213285,1244283,1275181,1302142,1334554,1362477,1391506,1420621,1446173,1476484,1502904,1530199,1557612,1581855,1621202,1654240,1688855,1723174,1752886,1788901,1819529,1851588,1883359,1911166,1944532,1973140,2003059,2032862,2059035,2090283,2117319,2145465,2173585,2198383,2227716,2253328,2279835,2306407,2329984,2367445,2399319,2432533,2465529,2494379,2528778,2558406,2589245,2619881,2646897,2678925,2706624,2735522,2764292,2789743,2819833,2846057,2873233,2900473,2924631,2952939,2977814,3003491,3029225,3052160,3087935,3118775,3150785,3182542,3210653,3243650,3272347,3302173,3331743,3358037,3388829,3415677,3443602,3471414,3496170,3525127,3550533,3576929,3603263,3626798,3654135,3678248,3703248,3728164,3750525,3784857,3814796,3845731,3876416,3903810,3935542,3963419,3992271,4020914,4046550,4076226,4102289,4129399,4156326,4180463,4208446,4233078,4258730,4284236,4307252,4333727,4357099,4381443,4405618,4427492,4460526,4489699,4519477,4549223,4575951,4606580,4633801,4661707,4689473,4714477,4743148,4768606,4794822,4820986,4844581,4871639,4895644,4920601,4945347,4967830,4993494,5016304,5040065,5063547,5084970,5116842,5145295,5174152,5203053,5229087,5258690,5285250,5312261,5339278,5363731,5391460,5416391,5441865,5467241,5490371,5516544,5540020,5564270,5588334,5610431,5635302,5657630,5680733,5703587,5724686,5755509,5783154,5811020,5839203,5864428,5893126,5919016,5945229,5971572,5995318,6022241,6046569,6071352,6096133,6118763,6144152,6167149,6190749,6214208,6235854,6259936,6281842,6304402,6326728,6347468,6377365,6404221,6431293,6458763,6483226,6511123,6536366,6561820,6587544,6610706,6636875,6660673,6684816,6709022,6731176,6755844,6778406,6801426,6824365,6845574,6868983,6890536,6912509,6934386,6954793,6996285,7030588,7066672,7102619,7133324,7171149,7202961,7236173,7269451,7298238,7333102,7362913,7393745,7424845,7451902,7484337,7512453,7541342,7570618,7596271,7626541,7653107,7680213,7707794,7732131,7771537,7804493,7839107,7873447,7903158,7939289,7969917,8001956,8033855,8061674,8095190,8123944,8153844,8183760,8209989,8241296,8268482,8296533,8324781,8349662,8379036,8404796,8431246,8457900,8481543,8519098,8550863,8584112,8617098,8645838,8680430,8709974,8740833,8771553,8798509,8830752,8858566,8887488,8916326,8941769,8972021,8998342,9025589,9052898,9077036,9105507,9130511,9156212,9182051,9205050,9240868,9271565,9303494,9335274,9363199,9396299,9424903,9454621,9484266,9510443,9541425,9568346,9596277,9624166,9648877,9678044,9703588,9729926,9756387,9779898,9807402,9831686,9856617,9881675,9904095,9938397,9968117,9998988,10029631,10056857,10088644,10116381,10145145,10173780,10199288,10229103,10255202,10282245,10309229,10333319,10361462,10386205,10411834,10437437,10460351,10486975,10510526,10534804,10559107,10581019,10613991,10642860,10672739,10702399,10728985,10759579,10786514,10814376,10842081,10866960,10895747,10921080,10947379,10973540,10997055,11024236,11048231,11073146,11097968,11120364,11146143,11169033,11192780,11216341,11237789,11269586,11297740,11326535,11355288,11381211,11410782,11437062,11464064,11490945,11515233,11543049,11567758,11593240,11618613,11641608,11667919,11691350,11715602,11739665,11761612,11786590,11808874,11831994,11854915,11875940,11906656,11934148,11962037,11990033,12015315,12043941,12069608,12095784,12121936,12145732,12172719,12196860,12221682,12246342,12268920,12294425,12317327,12340948,12364356,12385962,12410178,12432031,12454620,12476903,12497616,12527354,12554145,12581112,12608409,12632959,12660699,12685746,12711188,12736708,12759894,12786076,12809685,12833815,12857891,12880002,12904724,12927190,12950227,12973062,12994263,13017780,13039220,13061255,13083081,13103432,13132276,13158335,13184534,13211157,13235027,13261988,13286411,13311112,13336039,13358683,13384129,13407263,13430809,13454334,13475977,13500029,13522081,13544567,13566940,13587773,13610627,13631740,13653299,13674680,13694682,13734267,13767294,13801878,13836441,13866076,13902362,13933165,13965104,13997314,14025210,14058750,14087733,14117512,14147719,14174040,14205324,14232672,14260579,14289069,14314021,14343281,14369176,14395420,14422250,14446019,14483712,14515466,14548726,14581794,14610415,14645165,14674848,14705770,14736685,14763679,14795997,14823965,14852859,14881928,14907435,14937720,14964214,14991343,15018851,15043071,15071492,15096610,15122243,15148222,15171368,15207384,15238019,15270013,15301813,15329564,15362913,15391575,15421399,15451178,15477345,15508514,15535557,15563572,15591642,15616379,15645702,15671355,15697748,15724382,15747911,15775517,15799935,15824853,15850060,15872614,15907024,15936648,15967434,15998072,16025028,16056992,16084755,16113516,16142251,16167641,16197632,16223832,16250869,16278049,16302071,16330366,16355272,16380792,16406613,16429518,16456245,16479984,16504230,16528691,16550673,16583699,16612400,16642250,16671791,16698107,16728845,16755720,16783580,16811365,16836156,16865057,16890441,16916673,16942942,16966346,16993660,17017790,17042636,17067651,17089988,17115854,17138921,17162507,17186267,17207735,17239531,17267410,17296322,17324933,17350626,17380296,17406388,17433471,17460354,17484534,17512481,17537113,17562652,17588130,17611006,17637429,17660866,17685042,17709272,17731162,17756275,17778685,17801810,17824897,17845948,17876646,17903888,17931841,17959595,17984678,18013352,18038791,18065078,18091174,18114815,18141878,18165900,18190692,18215409,18237861,18263458,18286316,18309922,18333447,18354881,18379226,18401113,18423630,18446119,18466778,18496484,18523080,18550157,18577178,18601708,18629495,18654337,18679854,18705222,18728406,18754639,18778132,18802361,18826354,18848449,18873278,18895650,18918653,18941518,18962678,18986344,19007778,19029803,19051715,19072027,19100794,19126725,19152974,19179296,19203124,19230047,19254279,19279094,19303865,19326483,19351957,19374911,19398473,19421889,19443553,19467689,19489599,19512108,19534432,19555170,19578178,19599195,19620740,19642193,19662167,19690109,19715336,19740854,19766562,19789802,19815970,19839694,19863795,19887954,19910096,19934837,19957323,19980377,20003302,20024536,20048009,20069555,20091499,20113360,20133786,20156183,20176872,20197957,20218956,20238658,20276475,20308299,20341515,20374879,20403565,20438435,20468323,20499199,20530382,20557472,20589808,20617983,20646853,20676156,20701761,20731988,20758603,20785688,20813311,20837653,20865971,20891180,20916740,20942775,20966010,21002118,21032794,21064812,21096765,21124505,21157999,21186809,21216716,21246709,21272915,21304162,21331393,21359397,21387635,21412464,21441774,21467540,21493961,21520687,21544298,21571860,21596331,21621310,21646586,21669203,21703785,21733380,21764279,21795033,21821937,21854139,21881994,21910877,21939796,21965192,21995367,22021734,22048923,22076230,22100309,22128735,22153714,22179411,22205350,22228316,22255125,22278957,22303284,22327830,22349898,22383021,22411661,22441419,22471055,22497209,22528142,22555121,22583000,22610931,22635611,22664679,22690219,22716483,22742927,22766328,22793830,22818101,22842997,22868152,22890499,22916487,22939669,22963332,22987255,23008771,23040601,23068330,23097216,23125826,23151361,23181132,23207305,23234352,23261322,23285375,23313401,23338161,23363704,23389295,23412112,23438662,23462219,23486441,23510842,23532684,23557861,23580431,23603442,23626682,23647763,23678448,23705412,23733401,23761108,23786035,23814785,23840165,23866503,23892615,23916158,23943279,23967288,23992177,24016986,24039335,24065037,24087922,24111537,24135229,24156609,24181011,24202990,24225536,24248153,24268780,24298445,24324775,24351925,24378830,24403175,24431019,24455759,24481342,24506707,24529756,24556063,24579472,24603716,24627767,24649665,24674598,24696962,24720025,24743031,24764047,24787758,24809226,24831203,24853246,24873479,24902194,24927930,24954235,24980377,25004239,25031235,25055441,25080389,25105029,25127673,25153210,25176099,25199772,25223185,25244759,25268986,25290903,25313415,25335825,25356565,25379652,25400692,25422266,25443768,25463708,25491533,25516629,25542228,25567704,25590934,25617080,25640692,25664907,25688966,25711100,25735877,25758310,25781369,25804209,25825377,25848872,25870327,25892397,25914260,25934670,25957181,25977845,25998953,26019976,26039575,26066610,26091078,26115969,26140807,26163518,26188920,26212034,26235650,26259111,26280781,26304840,26326866,26349393,26371713,26392515,26415407,26436509,26458036,26479449,26499504,26521437,26541784,26562496,26583117,26602369,26638678,26669440,26701349,26733647,26761451,26795069,26824034,26853835,26884135,26910481,26941765,26969099,26997086,27025573,27050529,27079811,27105695,27131992,27158875,27182620,27210051,27234577,27259484,27284779,27307487,27342246,27371903,27402735,27433716,27460605,27492957,27520905,27549811,27578971,27604488,27634754,27661190,27688357,27715844,27740022,27768475,27793576,27819304,27845330,27868455,27895159,27919018,27943304,27967856,27990025,28023367,28052022,28081802,28111618,28137692,28168867,28195927,28223884,28252026,28276739,28306018,28331609,28358032,28384640,28408093,28435724,28460059,28485066,28510351,28532835,28558874,28582096,28605899,28629828,28651440,28683410,28711167,28739895,28768642,28794004,28823962,28850149,28877178,28904370,28928376,28956620,28981459,29006993,29032785,29055573,29082304,29105955,29130263,29154857,29176722,29201999,29224663,29247758,29271106,29292198,29322941,29349866,29377746,29405511,29430277,29459145,29484576,29510799,29537082,29560539,29587802,29611888,29636775,29661721,29683981,29709840,29732826,29756461,29780359,29801754,29826285,29848389,29870927,29893661,29914298,29943969,29970132,29997172,30024070,30048259,30076152,30100810,30126410,30151875,30174776,30201168,30224582,30248801,30273003,30294831,30319879,30342270,30365370,30388535,30409485,30433314,30454859,30476902,30499097,30519347,30548039,30573588,30599842,30625961,30649620,30676617,30700676,30725494,30750176,30772618,30798225,30821077,30844723,30868229,30889653,30913940,30935793,30958351,30980917,31001498,31024698,31045766,31067303,31088960,31108838,31136670,31161651,31187161,31212526,31235761,31261946,31285470,31309744,31333740,31355812,31380653,31403021,31426081,31448929,31470052,31493698,31515138,31537227,31559193,31579510,31602128,31622773,31643964,31665100,31684643,31711588,31735936,31760800,31785515,31808193,31833579,31856614,31880186,31903576,31925208,31949303,31971231,31993790,32016074,32036810,32059821,32080835,32102454,32123923,32143901,32165969,32186264,32206974,32227674,32246927,32273126,32296899,32321091,32345206,32367418,32392078,32414662,32437701,32460508,32481723,32505131,32526674,32548689,32570525,32590909,32613286,32633998,32655119,32676143,32695805,32717320,32737279,32757589,32777868,32796782,32831723,32861563,32892314,32923576,32950588,32983057,33011185,33040032,33069458,33095113,33125420,33152005,33179106,33206772,33231148,33259527,33284747,33310320,33336348,33359588,33386161,33410030,33434234,33458691,33480907,33514419,33543202,33573030,33603071,33629225,33660544,33687732,33715703,33744062,33768904,33798264,33824024,33850394,33877143,33900799,33928409,33952831,33977828,34003114,34025744,34051684,34074951,34098584,34122426,34144109,34176352,34204189,34233000,34261928,34287282,34317503,34343814,34370928,34398329,34422415,34450845,34475788,34501434,34527350,34550326,34577183,34600932,34625303,34649897,34671945,34697228,34719929,34743095,34766344,34787529,34818475,34845427,34873250,34901194,34925813,34954902,34980410,35006617,35033110,35056488,35083938,35108153,35132964,35158085,35180432,35206472,35229559,35253233,35277163,35298620,35323233,35345370,35367854,35390622,35411317,35441116,35467283,35494213,35521271,35545296,35573351,35598134,35623598,35649233,35672065,35698590,35722106,35746315,35770670,35792513,35817733,35840226,35863275,35886565,35907567,35931484,35953121,35975125,35997311,36017597,36046373,36071824,36098003,36124189,36147675,36174796,36198859,36223667,36248506,36270875,36296597,36319478,36343047,36366689,36388092,36412552,36434468,36457034,36479731,36500333,36523600,36544734,36566260,36587940,36607818,36635651,36660513,36685903,36711328,36734325,36760599,36784091,36808240,36832351,36854284,36879206,36901533,36924560,36947572,36968562,36992340,37013803,37035786,37057891,37078148,37100826,37121520,37142649,37163803,37183292,37210290,37234580,37259329,37284009,37306605,37332079,37355066,37378644,37402067,37423645,37447865,37469765,37492187,37514597,37535283,37558417,37579471,37601073,37622631,37642603,37664785,37685075,37705804,37726521,37745714,37771886,37795611,37819735,37843773,37865914,37890636,37913120,37936073,37958896,37980060,38003569,38025038,38047017,38068897,38089203,38111696,38132353,38153462,38174542,38194179,38215865,38235792,38256079,38276375,38295233,38320652,38343884,38367398,38390857,38412552,38436529,38458594,38481034,38503335,38524132,38546970,38568109,38589541,38610936,38630964,38652895,38673225,38693900,38714543,38733829,38754989,38774610,38794522,38814417,38832914,38866580,38895474,38925334,38955595,38981897,39013256,39040565,39068627,39097168,39122221,39151576,39177438,39203820,39230639,39254476,39281977,39306471,39331390,39356649,39379417,39405096,39428325,39451848,39475611,39497336,39529701,39557576,39586532,39615640,39641115,39671445,39697857,39725061,39752597,39776870,39805349,39830397,39856126,39882122,39905237,39932014,39955812,39980157,40004705,40026905,40051987,40074681,40097693,40120864,40142121,40173313,40200321,40228317,40256416,40281128,40310437,40336013,40362485,40389110,40412657,40440292,40464603,40489642,40514866,40537362,40563443,40586593,40610366,40634275,40655927,40680468,40702596,40725161,40747844,40768651,40798638,40824800,40851868,40879033,40903034,40931302,40956086,40981645,41007421,41030287,41057026,41080641,41104921,41129404,41151325,41176628,41199162,41222298,41245645,41266743,41290666,41312303,41334288,41356495,41376852,41405719,41431167,41457407,41483714,41507137,41534412,41558492,41583358,41608331,41630662,41656523,41679474,41703129,41726911,41748361,41772933,41794921,41817448,41840179,41860855,41884164,41905289,41926821,41948551,41968477,41996385,42021080,42046601,42072111,42095006,42121383,42144789,42168997,42193243,42215075,42240136,42262508,42285566,42308706,42329739,42353591,42375037,42397127,42419310,42439558,42462307,42482978,42504013,42525256,42544806,42571838,42595951,42620738,42645529,42667972,42693529,42716404,42739988,42763519,42784944,42809257,42831123,42853638,42876193,42896829,42920058,42941061,42962629,42984287,43004191,43026393,43046645,43067324,43088108,43107280,43133518,43157107,43181257,43205331,43227382,43252187,43274586,43297601,43320507,43341613,43365245,43386674,43408648,43430648,43450972,43473621,43494234,43515424,43536601,43556223,43577916,43597784,43617993,43638351,43657185,43682584,43705612,43729155,43752623,43774223,43798275,43820255,43842693,43865012,43885764,43908685,43929689,43951189,43972663,43992660,44014768,44035013,44055670,44076387,44095642,44116860,44136356,44156235,44176174,44194636,44219289,44241884,44264834,44287750,44308987,44332332,44353890,44375807,44397632,44418015,44440341,44461043,44482082,44503098,44522726,44544211,44564165,44584424,44604719,44623629,44644341,44663524,44682953,44702487,44720629,44753120,44781230,44810203,44839525,44865198,44895580,44922179,44949459,44977142,45001584,45030056,45055280,45080980,45107026,45130334,45156934,45180833,45205145,45229566,45251787,45276689,45299391,45322377,45345537,45366844,45398195,45425310,45453437,45481675,45506553,45535981,45561755,45588256,45614979,45638699,45666329,45690805,45715910,45741143,45763832,45789756,45813025,45836759,45860556,45882265,45906599,45928765,45951278,45973921,45994799,46025064,46051322,46078580,46105870,46129967,46158473,46183393,46209204,46235086,46258128,46284993,46308763,46333206,46357699,46379779,46405063,46427732,46450947,46474163,46495364,46519156,46540829,46562880,46585029,46605449,46634582,46660000,46686345,46712787,46736169,46763714,46787904,46812845,46837955,46860365,46886366,46909470,46933268,46957087,46978609,47003223,47025330,47047925,47070610,47091288,47114548,47135753,47157282,47179009,47198976,47227091,47251812,47277363,47303016,47325866,47352476,47375974,47400309,47424665,47446554,47471787,47494307,47517457,47540666,47561736,47585684,47607275,47629374,47651560,47671840,47694524,47715278,47736400,47757665,47777248,47804415,47828438,47853319,47878186,47900481,47926219,47949102,47972771,47996453,48017897,48042360,48064291,48086922,48109520,48130154,48153465,48174558,48196186,48217881,48237785,48259994,48280320,48300974,48321778,48340950,48367304,48390758,48414907,48439062,48460940,48485886,48508220,48531326,48554368,48575386,48599165,48620603,48642683,48664754,48684984,48707711,48728367,48749534,48770729,48790254,48811948,48831840,48852121,48872513,48891281,48916853,48939776,48963398,48986907,49008406,49032628,49054519,49077067,49099507,49120186,49143357,49164387,49186021,49207579,49227508,49249693,49269962,49290702,49311447,49330651,49351973,49371510,49391361,49411343,49429749,49454522,49477020,49499983,49522867,49544003,49567530,49588966,49610986,49632908,49653215,49675760,49696408,49717566,49738663,49758232,49779874,49799806,49820105,49840418,49859259,49880068,49899226,49918767,49938344,49956416,49980424,50002516,50024981,50047355,50068106,50090932,50112023,50133524,50154968,50174919,50196835,50217184,50237854,50258483,50277770,50298871,50318465,50338342,50358262,50376753,50397108,50415932,50435003,50454176,50471934,50503290,50530592,50558621,50587064,50612052,50641401,50667322,50693711,50720566,50744445,50771929,50796534,50821460,50846693,50869440,50895111,50918354,50941961,50965706,50987429,51011602,51033806,51056219,51078779,51099607,51129929,51156338,51183546,51210970,51235217,51263701,51288807,51314550,51340524,51363751,51390486,51414346,51438739,51463245,51485421,51510470,51533175,51556219,51579372,51600620,51624250,51645976,51667975,51690043,51710497,51739783,51765345,51791781,51818333,51841877,51869520,51893848,51918941,51944120,51966704,51992736,52015987,52039775,52063594,52085255,52109679,52131843,52154451,52177048,52197819,52221006,52242271,52263853,52285487,52305519,52333768,52358576,52384136,52409847,52432732,52459456,52483056,52507369,52531805,52553782,52579050,52601670,52624859,52648056,52669181,52692983,52714626,52736651,52758753,52779055,52801709,52822512,52843611,52864836,52884417,52911730,52935820,52960685,52985651,53008003,53033890,53056860,53080592,53104371,53125847,53150389,53172444,53195032,53217689,53238405,53261646,53282818,53304436,53326051,53345986,53368182,53388545,53409223,53430048,53449199,53475653,53499036,53523290,53547520,53569397,53594505,53616886,53639988,53663127,53684178,53708031,53729537,53751678,53773792,53794087,53816791,53837484,53858641,53879822,53899333,53921057,53941024,53961309,53981698,54000472,54026145,54048971,54072567,54096140,54117567,54141910,54163776,54186363,54208890,54229534,54252756,54273808,54295436,54317032,54336960,54359129,54379418,54400179,54420926,54440075,54461344,54480896,54500710,54520685,54539065,54563969,54586293,54609349,54632272,54653322,54677041,54698464,54720463,54742447,54762796,54785442,54806063,54827267,54848381,54867985,54889707,54909589,54929901,54950238,54969043,54989869,55009028,55028533,55048108,55066115,55090276,55112160,55134576,55156958,55177648,55200662,55221686,55243306,55264771,55284761,55306840,55327074,55347856,55368528,55387783,55409008,55428507,55448448,55468390,55486799,55507215,55525984,55545103,55564254,55581916,55605330,55626898,55648853,55670710,55691090,55713457,55734115,55755188,55776205,55795846,55817361,55837309,55857618,55877893,55896815,55917530,55936711,55956203,55975719,55993821,56013826,56032268,56050997,56069759,56087100,56117392,56143983,56171131,56198735,56223092,56251511,56276798,56302330,56328409,56351666,56378242,56402223,56426335,56450858,56473056,56497911,56520630,56543563,56566721,56587993,56611499,56633206,56655039,56677136,56697604,56726976,56752705,56779100,56805789,56829445,56857046,56881564,56906560,56931817,56954472,56980372,57003724,57027323,57051120,57072818,57097093,57119319,57141698,57164318,57185152,57208129,57229379,57250816,57272438,57292497,57320919,57345854,57371560,57397378,57420362,57447219,57471042,57495376,57519908,57542029,57567259,57589989,57613097,57636294,57657470,57681202,57702919,57724912,57747062,57767454,57789982,57810838,57831827,57853050,57872728,57900221,57924413,57949272,57974334,57996698,58022684,58045821,58069501,58093375,58114926,58139438,58161603,58184123,58206761,58227468,58250646,58271877,58293306,58314974,58334967,58357049,58377486,58398062,58418880,58438098,58464722,58488211,58512481,58536824,58558706,58583926,58606466,58629536,58652772,58673871,58697766,58719438,58741443,58763572,58783868,58806512,58827277,58848370,58869605,58889152,58910809,58930850,58951013,58971445,58990254,59016074,59038907,59062567,59086213,59107613,59132084,59154048,59176597,59199243,59219899,59243166,59264306,59285893,59307525,59327409,59349592,59369897,59390529,59411330,59430530,59451778,59471383,59491178,59511231,59529673,59554743,59577022,59600127,59623107,59644142,59667953,59689385,59711465,59733540,59753845,59776594,59797293,59818394,59839578,59859126,59880807,59900701,59920926,59941317,59960093,59980938,60000126,60019515,60039175,60057199,60081547,60103325,60125861,60148290,60168991,60192192,60213178,60234740,60256282,60276243,60298481,60318762,60339505,60360234,60379432,60400670,60420168,60440023,60459992,60478378,60498834,60517642,60536716,60555962,60573661,60597273,60618662,60640663,60662527,60682885,60705454,60726019,60747192,60768271,60787877,60809582,60829490,60849776,60870072,60888927,60909710,60928837,60948323,60967883,60985975,61006033,61024402,61043080,61061932,61079255,61102174,61123221,61144724,61166147,61186172,61208148,61228441,61249085,61269701,61288973,61310111,61329701,61349578,61369460,61387988,61408345,61427101,61446207,61465339,61483094,61502707,61520710,61539101,61557501,61574510,61615868};

int F(int x){
    if(x==0)return 1;
    int sum=0;
    while(x){
        sum+=x%10;
        x/=10;
    }
    return sum;
}

int Cal(int L,int R){
    int sum=0;
    for(int i=L;i<R;i++)
        sum+=((i%F(i))==0);
    return sum;
}

int Table(int x){
    return a[x/N]+Cal(x/N*N,x+1);
}

int main(){
    int q; cin>>q;
    for(int i=1;i<=q;i++){
        int l,r; cin>>l>>r;
        cout<<"Case "<<i<<": "<<Table(r)-Table(l-1)<<endl;
        //cout<<"Case "<<i<<": "<<Cal(l,r+1)<<endl;
    }

    return 0;
}

G - 最小公倍数之和

题解

莫比乌斯模板题。但是有需要注意的：

中间可能爆 ll，该及时取模就取模
对常量取模应该提前算好以提升运行速度
两次分块过程可以用两个函数实现，这样子类似 (n/g)/(n/g/p) 的东西会写起来舒服很多

代码

点击显示 / 隐藏

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int MOD=20101009,N=10000000+5;
const int INV2=10050505,INV4=15075757;
int mu[N]; ll sum[N];

ll QPow(ll bas,int t){
    ll ret=1; bas%=MOD;
    for(;t;t>>=1,bas=bas*bas%MOD)
        if(t&1)ret=ret*bas%MOD;
    return ret;
}

ll Inv(ll x){
    return QPow(x,MOD-2);
}

void Init(){
    static bool notPri[N];
    static int pri[N];

    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!notPri[i])pri[++pri[0]]=i,mu[i]=-1;
        for(int j=1; j<=pri[0] && i*pri[j]<N; j++){
            int nxt=i*pri[j]; notPri[nxt]=1;
            if(i%pri[j])mu[nxt]=-mu[i];
            else{
                mu[nxt]=0;
                break;
            }
        }
    }

    for(int i=1;i<N;i++)
        sum[i]=(1LL*i*i*mu[i]+sum[i-1])%MOD;
}

ll F(ll a,ll b){
    ll tmpA=a*(a+1)%MOD;
    ll tmpB=b*(b+1)%MOD;
    return tmpA*tmpB%MOD*INV4%MOD;
}

int main(){
    Init();
    int n,m; cin>>n>>m;
    if(n>m)swap(n,m);

    ll ans=0;
    for(int g=1;g<=n;g++){
        int nxtG=min(min(n/(n/g),m/(m/g)),n);
        for(int p=1;p<=n/g;p++){
            int nxtP=min(min((n/g)/(n/g/p),(m/g)/(m/g/p)),n/g);
            ll tmpAns=(sum[nxtP]-sum[p-1])*F(n/g/p,m/g/p)%MOD;
            tmpAns=tmpAns*(g+nxtG)%MOD*(nxtG-g+1)%MOD*INV2%MOD;
            ans=(ans+tmpAns%MOD)%MOD;
            p=nxtP;
        }
        g=nxtG;
    }

    cout<<(ans%MOD+MOD)%MOD;

    return 0;
}