企业官网建设流程全解析

问题形式

与 CRT 一致，只是不再保证m 1 , m 2 , . . . , m k m_1,m_2,...,m_km1​,m2​,...,mk​互质

解法

exCRT 的核心思想是去不断“合并”方程

设x xx为满足前i − 1 i-1i−1个方程的最小非负解，M = lcm ⁡ j = 1 i − 1 m j M = \operatorname{lcm}_{j=1}^{i-1} m_jM=lcmj=1i−1​mj​（i ≥ 2 i \ge 2i≥2），现在要将第i ii个方程合并进去

设合并第i ii个方程后的解为x + t M x+tMx+tM，则x + t M ≡ a i ( m o d m i ) x + tM \equiv a_i \pmod {m_i}x+tM≡ai​(modmi​)。设b = a i − x b = a_i - xb=ai​−x，则t M ≡ b ( m o d m i ) tM \equiv b \pmod {m_i}tM≡b(modmi​)。设g = gcd ⁡ ( m i , M ) g = \gcd(m_i,M)g=gcd(mi​,M)

显然，若g ∤ b g \nmid bg∤b则方程无解，判掉这种情况

设a ′ = M g , m ′ = m i g , b ′ = b g , a ′ t ≡ b ′ ( m o d m ′ ) a' = \frac Mg,m' = \frac{m_i}{g},b' = \frac bg,a't \equiv b' \pmod {m'}a′=gM​,m′=gmi​​,b′=gb​,a′t≡b′(modm′)

求t tt需要求a ′ a'a′的逆元，考虑 exgcd 求出使得a ′ x + m ′ y = 1 a'x+m'y=1a′x+m′y=1的x xx，则x xx即为a ′ a'a′的逆元（的倍数）

然后就求出了t tt，也就得出了答案

代码

P4777 【模板】扩展中国剩余定理（EXCRT）

#include<bits/stdc++.h>usingnamespacestd;#definepre(i,n)for(inti=n;i;--i)#definerep(i,n)for(inti=1;i<=n;++i)#definerpt(i,a,n)for(inti=a;i<=n;++i)#defineint__int128#defineswap(x,y)(x^=y^=x^=y)#definedebugcerr<<"Help!"<<endlconstexprintN=1e5+5;inta[N],m[N],n,res,M,d,x,y;voidexgcd(inta,intb,int&x,int&y){if(!b){x=1,y=0,d=a;return;}exgcd(b,a%b,y,x);y-=a/b*x;}inlineintlcm(inta,intb){returna/__gcd(a,b)*b;}inlinevoidread(int&x){x=0;charc;for(c=getchar();!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);}inlinevoidwrite(intx){if(x>9)write(x/10);putchar((x%10+'0'));}signedmain(){read(n);rep(i,n)read(m[i]),read(a[i]);res=a[1],M=m[1];rpt(i,2,n){intg=__gcd(M,m[i]),b=a[i]-res;b%=m[i];if(b%g)returncout<<"WRONG!",0;inta=M/g,m_=m[i]/g;b/=g;exgcd(a,m_,x,y);//inv = xintt=x*b%m_;t=(t+m_)%m_;res+=t*M,M=lcm(M,m[i]),res%=M;}write(res);cerr<<endl<<1.0*clock()/CLOCKS_PER_SEC;return0;}