AtCoder-abc466_f Many Mod Calculation 题解

Solution考虑所有x0,1,…,Xx 0,1,\dots,Xx0,1,…,X依次对A1,A2,…,ANA_1,A_2,\dots,A_NA1​,A2​,…,AN​取模的过程。初始时这些数构成一个半开区间[0,X1)[0, X1)[0,X1)。第iii步对AiA_iAi​取模会把当前每个区间[0,d)[0,d)[0,d)分拆成⌊d/Ai⌋\lfloor d/A_i\rfloor⌊d/Ai​⌋个[0,Ai)[0,A_i)[0,Ai​)111个[0,d mod Ai)[0,d\bmod A_i)[0,dmodAi​)若d mod Ai≠0d\bmod A_i\neq 0dmodAi​0我们可以维护所有区间并将右端点相同的区间合并。具体地用一个map维护每个右端点ddd对应的区间[0,d)[0,d)[0,d)出现次数。然后直接按照上述过程模拟即可。复杂度分析第iii步中对于区间[0,d)[0,d)[0,d)取模AiA_iAi​时若d≥Aid\ge A_id≥Ai​则必有d mod Aid/2d\bmod A_id/2dmodAi​d/2。这一步还会产生[0,Ai)[0,A_i)[0,Ai​)区间。因此在整个过程中出现过的本质不同区间共有O(Nlog⁡X)O(N\log X)O(NlogX)个因此总时间复杂度O(Nlog⁡Xlog⁡N)O(N\log X\log N)O(NlogXlogN)。Code#includebits/stdc.h#definerept(i,a,b)for(inti(a);ib;i)#definefifirst#definesesecond#defineintlonglongusingnamespacestd;constexprintN2e55;intn,x,a[N];mapint,int,greaterintmp;voidsolve(){cinnx;mp.clear();mp[x1]1;rept(i,1,n)cina[i];rept(i,1,n){for(autoitmp.begin();it!mp.end();it){if(it-fia[i])break;intqit-fi/a[i],rit-fi%a[i];mp[a[i]]q*it-se;if(r)mp[r]it-se;}while(mp.begin()-fia[i])mp.erase(mp.begin());}intans0;for(autoitmp.begin();it!mp.end();it){ansit-se;}coutans-1\n;}signedmain(){intT;cinT;while(T--)solve();return0;}