题解 P1495 【曹冲养猪】

2018-09-10 07:45:00


顾z

题目描述-->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(就是上面那个辣)

代码中变量可能与分析不符 见谅!

---------------------代码--------------------

#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);
}