中国剩余定理

对于\(n\)个方程组成的方程组组
\[ \left\{ \begin{aligned} x\equiv A_1 (mod && B_1) \\ x\equiv A_2 (mod && B_2)\\\dots \\x\equiv A_i (mod && B_i) \end{aligned} \right. \]
---
设\(mul=\Pi_{i=1}^{i<=n} B_i\),\(T_i\)为\(M_i\)在\(\mod B_i\)意义下的逆元,\(M_i=\frac{mul}{B_i}\)

则\(ans=\sum M_i\times T_i \times A_i\)

\(M_i\) 个人认为用来抵消

然后,妙啊

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
#include<queue>
#include<iostream>
#include<cmath>
//#define int long long 
using namespace std;
inline int gi(){char tmp=getchar();int flag=1;while(tmp<'0'||tmp>'9'){if(tmp=='-'){flag=-1;tmp=getchar();break;}tmp=getchar();}int ans=0;while(tmp<='9' and tmp>='0') {ans=ans*10+tmp-'0';tmp=getchar();}return ans*flag;}
inline void write(int x){static int stk[100], top = 0;if (x == 0) { putchar('0'); putchar(' ');return; }if (x < 0) { x = -x; putchar('-'); }while (x) { stk[++top] = x % 10; x /= 10; }while (top) { putchar(stk[top--] + '0'); }putchar(' ');}
#define line() putchar('\n');
#define Mem(Arr,V) memset(Arr,V,sizeof Arr);
#define Mcpy(Arr,qwq) memcpy(Arr,qwq,sizeof qwq);
#define max3(a,b,c) max(max(a,b),c)
#define max4(a,b,c,d) max4(max3(a,b,c),d);
#define in(a) a=gi()
#define in2(a,b) in(a),in(b)
#define in3(a,b,c) in2(a,b),in(c)
#define in4(a,b,c,d) in3(a,b,c),in(d)
#define write2(a,b) write(a),write(b)
#define write3(a,b,c) write2(a,b),write(c)
#define write4(a,b,c,d) write3(a,b,c),write(d)
#define smin(a,b) a=min(a,b)
#define smax(a,b) a=max(a,b)
void Exgcd(int a,int b,int &x,int &y)
{
    if(!b) {x=1,y=0;return;}
    Exgcd(b,a%b,y,x);y-=x*(a/b);
}
inline int Inv(int x,int mod)
/*
    x*inv=1(%mod)
    x*inv+mod*y=1
*/
{
    int inv,y;
    Exgcd(x,mod,inv,y); 
    return inv;
}
#define N 100001
int A[N],B[N];
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("data.in","r",stdin);
    #endif
    int n;
    in(n);
    int mul=1;
    for(int i=1;i<=n;++i)
    {
        in2(B[i],A[i]);
        mul*=B[i];  
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int m=mul/B[i];
        ans=((ans+m*Inv(m,B[i])*A[i]%mul)+mul)%mul; 
        ans%=mul;
    }
    write(ans);
    return 0;
}

中国剩余定理

原文：https://www.cnblogs.com/guodongLovesOi/p/11564583.html