P4777

发表于 分类于
【模板】扩展中国剩余定理（EXCRT）

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

只需要考虑合并两个方程的情况即可。

$$
\begin{cases}
x \equiv a _ 1 \pmod { m _ 1 }
\\
x \equiv a _ 2 \pmod { m _ 2 }
\end{cases}
$$

对于这样的方程组，我们设：

$$ x = m _ 1 p + a _ 1 = m _ 2 q + a _ 2 $$

那么就会有二元不定方程：

$$ m _ 1 p - m _ 2 q = a _ 2 - a _ 1 $$

那么显然，在 $\gcd ( m _ 1 , m _ 2 ) \nmid ( a _ 2 - a _ 1 )$ 的时候是无解的。

反之我们能解出来对应的 $p , q $。

那么显然得到的解是 $x \equiv b \pmod { M }$。

其中的 $b = m _ 1 p + a _ 1 , M = \operatorname{lcm} (m _ 1 , m _ 2 )$。

时间复杂度 $O( n \log a)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(10);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e5;

ll n,M,b;
ll a[N+5],m[N+5];

inline ll Exgcd(ll a,ll b,ll &x,ll &y) {
  if(b==0) {x=1;y=0;return a;}ll r=Exgcd(b,a%b,y,x);y-=a/b*x;return r;
}

int main() {

  n=read();

  for(ll i=1;i<=n;i++) {
    m[i]=read();a[i]=read();
  }
  M=m[1];b=a[1];

  for(ll i=2;i<=n;i++) {
    ll m1,m2;m1=M;m2=m[i];
    ll d,x0,y0;d=Exgcd(m1,m2,x0,y0);
    x0=x0*(a[i]-b)/d;y0=y0*(a[i]-b)/d;
    b=m1*x0+b;M=m1/d*m2;
    if(b<0) {b=(b+(-b/M+1)*M)%M;}
    b%=M;
  }

  write(b);
  
  return 0;
}