题解 P1495 【曹冲养猪】

## [顾z](http://www.cnblogs.com/-guz/) 题目描述-->[p1495 曹冲养猪](https://www.luogu.org/problemnew/show/P1495) ## 分析: 大多数人不理解**Crt+Exgcd**(我来解释一下.) 很容易看出此题考查的是**中国剩余定理**. ($CRT$ 为中国剩余定理$ qwq) 关于模意义下的同余方程组,我们一般选择用exgcd求解. xi ≡ bi(mod ai) //bi,ai含义对应题目所述. 题目中说,可以认为ai之间互质. //即 a1 ,a2, a3...an 互质 因此呢,我们可以 求出N=Πai 即 N/ai ≡ 1(mod ai) //因为ai之间互质,所以说对应的除去ai,这个数依旧与ai互质. 因为Exgcd解决的问题是px+qy =gcd(p,q) //应该是这样没错 emmm 我们令p=N/ai,由 p ≡ 1(mod ai)容易列出式子 ``(N/ai)*x+ai*y = 1`` 而我们的答案 ``ans=∑ bi*xi(mod N)`` 最近打算总结一下该算法。~~不知道什么时候会写出来~~ 欢迎到blog(就是上面那个辣) 代码中变量可能与分析不符 见谅! ---------------------代码-------------------- ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int IL void read(long long &x){ int f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} x*=f; } long long n; long long M=1,ans; struct cod{long long a,b;}elephants[15]; IL long long exgcd(long long a,long long b,long long &x,long long &y) { if(!b){ x=1;y=0; return a; } long long c=exgcd(b,a%b,y,x); y-=a/b*x; return c; } IL void China() { for(RI i=1;i<=n;i++) { long long N,c,h,j; N=M/elephants[i].a; c=exgcd(N,elephants[i].a,h,j); ans=(ans+N*h*elephants[i].b)%M; } ans=(ans+M)%M; } int main() { read(n); for(RI i=1;i<=n;i++) read(elephants[i].a),read(elephants[i].b),M*=elephants[i].a; China(); printf("%lld",ans); } ```