本文共 1416 字，大约阅读时间需要 4 分钟。
自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了。如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去，然后如果建造了 7 个猪圈，还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？
输入格式
第一行包含一个整数 n——建立猪圈的次数，接下来 n 行，每行两个整数 a i b i a_i\ b_i ai bi 表示建立了 a i a_i ai 个猪圈，有 b i b_i bi 头猪没有去处。你可以假定 a i a_i ai， a j a_j aj互质。输出包含一个正整数，即为曹冲至少养母猪的数目。
输入
33 15 17 2
输出
16
1 ≤ n ≤ 10 ， 0 ≤ b i < a i ≤ 1000000 ， 1 ≤ ∏ a i ≤ 1 0 18 1 \leq n\le10，0 \leq b_i\lt a_i\le1000000，1 \leq \prod a_i \leq 10^{18} 1≤n≤10，0≤bi<ai≤1000000，1≤∏ai≤1018
不是吧不是吧不会有人看不出来 这是模板CRT，
#include#include #define ll long long //不开longlong见祖宗using namespace std;ll n,m=1,ans,t,x,y,a[20],b[20];void exgcd(ll a,ll b)//扩展欧几里得算法求逆元{ if(b==0) { x=1; y=0; return; } exgcd(b,a%b); int t=x; x=y; y=t-a/b*y;}int main(){ scanf("%lld",&n); for(int i=1; i<=n; i++) { scanf("%lld%lld",&a[i],&b[i]); m*=a[i];//求最小公倍数 } for(int i=1; i<=n; i++) { t=m/a[i]; x=y=0; exgcd(t,a[i]); x=(x%a[i]+a[i])%a[i]; ans=(ans+x*t*b[i])%m;//CRT 记得模数 }cout<
转载地址：http://xhpwb.baihongyu.com/