Acwing 204. 表达整数的奇怪方式（扩展中国剩余定理）

解题步骤：

扩展中国剩余定理的模板题

x ≡ m 1 ( m o d   a 1 ) x\equiv m_1(mod \ a_1) x≡m1​(mod a1​)

x ≡ m 2 ( m o d   a 2 ) x\equiv m_2(mod \ a_2) x≡m2​(mod a2​)

⇒ a 1 ∗ y 1 + m 1 = a 2 ∗ y 2 + m 2 \Rightarrow a_1 * y_1 + m_1 = a_2 * y_2 + m2 ⇒a1​∗y1​+m1​=a2​∗y2​+m2

⇒ y 1 ∗ a 1 − y 2 ∗ a 2 = m 2 − m 1 \Rightarrow y_1 * a_1 - y_2 * a_2 = m_2 - m_1 ⇒y1​∗a1​−y2​∗a2​=m2​−m1​

设

Y 1 ∗ a 1 + Y 2 ∗ a 2 = g c d ( a 1 , a 2 ) Y_1 * a_1 + Y_2 * a_2 = gcd(a_1,a_2) Y1​∗a1​+Y2​∗a2​=gcd(a1​,a2​)

当 ( m 2 − m 1 )   %   g c d ( a 1 , a 2 )   ! = 0 (m_2 - m_1) \ \%\ gcd(a_1,a_2) \ != 0 (m2​−m1​) % gcd(a1​,a2​) !=0 时无解

若有解

y 1 = Y 1 ∗ (   ( m 2 − m 1 ) / g c d ( a 1 , a 2 )   ) + t ∗ a 2 / g c d ( a 1 , a 2 ) y_1 = Y_1*(\ (m_2-m_1)/gcd(a_1,a_2)\ ) + t * a_2 / gcd(a_1,a_2) y1​=Y1​∗( (m2​−m1​)/gcd(a1​,a2​) )+t∗a2​/gcd(a1​,a2​)​

x ≡ m 1 ( m o d   a 1 ) ⇒ x = y 1 ∗ a 1 + m 1 x\equiv m_1(mod \ a_1) \Rightarrow x = y_1 * a_1 + m_1 x≡m1​(mod a1​)⇒x=y1​∗a1​+m1​

x = ( Y 1 ∗ (   ( m 2 − m 1 ) / g c d ( a 1 , a 2 )   ) + t ∗ a 2 / g c d ( a 1 , a 2 ) ) ∗ a 1 + m 1 x = \left(Y_1*\left(\ \left(m_2-m_1\right)/gcd\left(a_1,a_2)\ \right) + t * a_2 / gcd(a_1,a_2\right) \right)*a_1 + m_1 x=(Y1​∗( (m2​−m1​)/gcd(a1​,a2​) )+t∗a2​/gcd(a1​,a2​))∗a1​+m1​

= Y 1 ∗ (   ( m 2 − m 1 ) / g c d ( a 1 , a 2 )   ) ∗ a 1 + m 1 ⏟ 新 的 m 1 + t ∗ l c m ( a 1 , a 2 ) ⏟ 新 的 a 1 =\underbrace{Y_1*(\ (m_2-m_1)/gcd(a_1,a_2)\ ) * a_1 + m_1 }_{新的m_1} + t * \underbrace{lcm(a_1,a_2)}_{新的a_1} =新的m1​

Y1​∗( (m2​−m1​)/gcd(a1​,a2​) )∗a1​+m1​​​+t∗新的a1​

lcm(a1​,a2​)​​

每次更新 a 1 , m 1 a_1,m_1 a1​,m1​ 和新读入的 a 1 , m 2 a_1,m_2 a1​,m2​ 进行运算

最终得到结果 x = ( m 1   %   a 1 + a 1 ) % a 1 ) x = (m_1\ \% \ a_1 + a_1 ) \% a_1 ) x=(m1​ % a1​+a1​)%a1​)​​

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll; 
using namespace std;
ll exgcd(ll a, ll b ,ll &x, ll &y){
    if(!b){
        x = 1 , y = 0 ;
        return a ;
    }
    ll d = exgcd(b,a%b,y,x) ; 
    y -= (a/b) * x ; 
    return d; 
}



int main(){
    int n ;
    scanf("%d",&n) ; 
    ll a1 , m1 ;
    scanf("%lld%lld",&a1,&m1) ; 
    int flag = 1 ; 
    for(int i = 1 ; i < n ; i ++ ) {
        ll a2 , m2 , y1 , y2 ; 
        scanf("%lld%lld",&a2,&m2) ; 
        ll d = exgcd(a1,a2,y1,y2) ; 
        if( (m2 - m1 ) % d ) {
            flag = 0 ;
            break;
        }
        y1 = y1 * ( m2 - m1 ) / d ; 
        ll t = a2 / d ; 
        y1 = ((y1 % t) + t ) % t ; 
        m1 = y1 * a1 + m1 ; 
        a1 = a1 * a2 / d;  
    }
    if(flag){
        printf("%lld", (m1 % a1 + a1 ) % a1 ) ; 
    }
    else puts("-1") ; 
    return 0 ; 
}