P5330 [SNOI2019] 数论

题意给出正整数P , Q , T P,Q,TP,Q,T大小为n nn的整数集A AA和大小为m mm的整数集B BB现在需要求∑ i 0 T − 1 [ ( i m o d P ) ∈ A ∧ ( i m o d Q ) ∈ B ] \sum_{i0}^{T-1}[(i\bmod P) \in A \land (i\bmod Q) \in B]∑i0T−1​[(imodP)∈A∧(imodQ)∈B]。n ≤ 10 6 n\le10^6n≤106p , q ≤ 10 6 p,q\le10^6p,q≤106T ≤ 10 1 8 T\le10^18T≤1018。思路设g gcd ⁡ ( P , Q ) g\gcd(P,Q)ggcd(P,Q)对于一对( i ∈ A , j ∈ B ) (i\in A,j\in B)(i∈A,j∈B)如果i ≢ j ( m o d g ) i\not\equiv j\pmod gi≡j(modg)则不存在x xx满足x ≡ i ( m o d P ) , x ≡ j ( m o d Q ) x\equiv i\pmod P,x\equiv j\pmod Qx≡i(modP),x≡j(modQ)反之如果i ≡ j ( m o d g ) i\equiv j\pmod gi≡j(modg)则在[ 0 , l c m ( P , Q ) ) [0,lcm(P,Q))[0,lcm(P,Q))中存在且仅存在一个x xx满足x ≡ i ( m o d P ) , x ≡ j ( m o d Q ) x\equiv i\pmod P,x\equiv j\pmod Qx≡i(modP),x≡j(modQ)。把m o d g \bmod gmodg相等的值领出来分开计算。按照l c m ( P , Q ) lcm(P,Q)lcm(P,Q)把[ 0 , T ) [0,T)[0,T)分成很多块整块是好计算的考虑计算散块。以P 4 , Q 6 P4,Q6P4,Q6为例计算≡ 1 ( m o d 2 ) \equiv1\pmod2≡1(mod2)的部分。mod 4mod 6113315311335发现当≡ 1 ( m o d 4 ) \equiv1\pmod4≡1(mod4)时m o d 6 \bmod6mod6的结果是1 , 5 , 3 , … 1,5,3,\dots1,5,3,…当≡ 3 ( m o d 4 ) \equiv3\pmod4≡3(mod4)时m o d 6 \bmod6mod6的结果是3 , 1 , 5 , … 3,1,5,\dots3,1,5,…找到规律当模P PP的余数增加g gg时模Q QQ的最小循环节会把最后几位搬到前面而每次被搬到前面的数的个数mis可以通过在环上找到( i g ) m o d Q (ig)\bmod Q(ig)modQ的位置来计算即mis环长-pos。根据这个规律我们给每个值标号枚举模P PP的余数v vv开个桶判断是否在A AA中同时在环上用前缀和快速统计连续区间内有多少个值在B BB中从而计算散块中的答案。代码// Problem: P5330 [SNOI2019] 数论// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P5330// Memory Limit: 256 MB// Time Limit: 2000 ms//// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.husingnamespacestd;namespaceIO{templatetypenameTinlinevoidread(Tx){x0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))xx*10c-0,cgetchar();f?x-x:0;}templatetypenameTinlinevoidwrite(T x){if(x0){putchar(0);return;}x0?x-x,putchar(-):0;shortst[50],top0;while(x)st[top]x%10,x/10;while(top)putchar(st[top--]0);}inlinevoidread(charc){cgetchar();while(isspace(c))cgetchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(strings){s.clear();charc;read(c);while(!isspace(c)~c)sc,cgetchar();}inlinevoidwrite(string s){for(inti0,lens.size();ilen;i)putchar(s[i]);}templatetypenameTinlinevoidwrite(T*x){while(*x)putchar(*(x));}templatetypenameT,typename...T2inlinevoidread(Tx,T2...y){read(x),read(y...);}templatetypenameT,typename...T2inlinevoidwrite(constT x,constT2...y){write(x),putchar( ),write(y...),sizeof...(y)1?putchar(\n):0;}}usingnamespaceIO;#defineLLlonglongconstintmaxn1000010;intp,q,n,m,sum[maxn];LL t,ans;boolina[maxn],inb[maxn],app[maxn];vectorintvta[maxn],vtb[maxn],vt;signedmain(){read(p,q,n,m,t);intg__gcd(p,q);LL l1ll*p*q/g;for(inti1;in;i){intv;read(v);vta[v%g].push_back(v);ina[v]1;}for(inti1;im;i){intv;read(v);vtb[v%g].push_back(v);inb[v]1;}for(inti0;ig;i){anst/l*vta[i].size()*vtb[i].size();vt.clear();vt.push_back(i);LL nwi;while(1){nwp;if(nw%qvt[0])break;vt.push_back(nw%q);}sum[0]inb[vt[0]];for(inti1;ivt.size();i)sum[i]sum[i-1]inb[vt[i]];intmis;for(intwz1;wzvt.size();wz)if(vt[wz](ig)%q)misvt.size()-wz;LL syt%l;if(sy0)continue;sy--;intwvt.size()mis;for(LL vi;1;vg){if(app[v%p])break;app[v%p]1;w-mis;w(wvt.size())%vt.size();intcnt(sy-v)/p1;if(vsy)cnt0;if(cnt0)continue;intghvt.size()-w;if(ina[v]0)continue;if(ghcnt)anssum[wcnt-1]-(w?sum[w-1]:0);elseanssum[vt.size()-1]-(w?sum[w-1]:0)sum[cnt-gh-1];}for(LL vi;1;vg){if(app[v%p]0)break;app[v%p]0;}}write(ans);return0;}