#扩展欧几里得算法，快速乘#洛谷 4777 poj 2891 【模板】扩展中国剩余定理

本文主要是介绍#扩展欧几里得算法，快速乘#洛谷 4777 poj 2891 【模板】扩展中国剩余定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定 $n$ 组非负整数 $a_i, b_i$ ,求解关于 $x$ 的方程组
$x\equiv b_1(\mod a_1)$
$x\equiv b_2(\mod a_2)$ $\cdots$
$x\equiv b_n(\mod a_n)$
的最小非负整数解

分析

虽然题目好像是中国剩余定理，但是 $a$ 数组不满足互质，必然是需要其它的方法，那么就可以用扩欧，跑n遍，因为要求最小，所以需要求最小公倍数，然后其实就没什么了

代码

#include <cstdio>
#define rr register
typedef long long ll;
ll in(){ll ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();return ans;
}
void print(ll ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
ll exgcd(ll a,ll b,ll &x,ll &y){//扩欧if (!b) {x=1; y=0; return a;}else{rr ll d=exgcd(b,a%b,y,x);y-=a/b*x; return d;}
}
ll ksm(ll x,ll y,ll mod){//快速乘ll ans=0;while (y){if (y&1) ans=(ans+x)%mod;x=(x+x)%mod; y>>=1;}return ans;
}
int main(){rr int n;while (scanf("%d",&n)==1){rr ll a=in(),ans=in(); rr bool flag=1;while (--n){rr ll b=in(),c=in();if (!flag) continue;c=(c-ans%b+b)%b; rr ll x,y,mod;//求出新的答案rr ll d=exgcd(a,b,x,y); mod=b/d;//扩欧if (c%d) {flag=0; continue;}//不可能x=ksm(x,c/d,mod);//快速乘ans+=x*a; a*=mod; ans=(ans%a+a)%a;//求最小非负整数解}if (!flag) putchar('-'),putchar(49);else if (ans) print(ans); else putchar(48); putchar(10);}
}