题解 P1495 【曹冲养猪】

灵乌路空 · 2019-05-20 20:27:28 · 题解

无良宣传一下博客wwwwww
文章列表 - 核融合炉心 - 洛谷博客

• 分析题意:

  现有两组数字，每组 k 个，
  第一组中的数字分别为：a_1,a_2,...,a_k 表示，
  第二组中的数字分别用b_1,b_2, ... ,b_k表示。
  第二组中的数字\underline\text{两两互质}。
  求最小的非负整数 n ，

  根据题意 ， 题干可以转化为: - ##### 要解如下的同余方程组 ： $\begin{cases}x \equiv a_1\pmod {b_1}\\x \equiv a_2\pmod {b_2}\\......\\x \equiv a_n\pmod {b_n}\\\end{cases}

  因为 bi 之间 两两互质，所以可以用 中国剩余定理 求解
  但是 中国剩余定理 适用范围太小，
  这里介绍用 扩展中国剩余定理 求解。

求解同余方程组 (扩展中国剩余定理)

一道模板题: P4777 【模板】扩展中国剩余定理（EXCRT）

• 要解如下的同余方程组 ：

  \begin{cases}x \equiv a_1\pmod {b_1}\\x \equiv a_2\pmod {b_2}\\......\\x \equiv a_n\pmod {b_n}\\\end{cases}

  其中 , a_i,b_i为非负整数 ， b_1,b_2,...,b_n 不一定互质

• 求解:

  假设已经求出了前 k-1 个方程的解 x_{k-1}
  设 M=LCM_{i=1}^{k-1} bi , 即 M 为前 k-1 个模数 b 的最小公倍数

  则 :
  对于前 k-1个方程, 都满足x_{k-1}+tM\equiv a_i\pmod {b_i}\ \ (t\in Z)
  即 : 前 k-1 个方程 , 通解为 x_{k-1}+tM\ \ (t\in Z)

  欲求得第 k 个方程的解 , 并且将求得的解 , 也满足前 k-1 个方程

  则 :
  需要使第 k 个方程的解 , 为前 k-1 的方程的通解的同时 ， 也满足第 k 个方程的条件 。

  设 : 第k 个方程的解 x_k = x_{k-1}+tM\ \ (t\in Z)

  将此解代入第 k 个方程中 , 可得 :

  x_{k-1}+tM\equiv a_k\pmod{b_k}

  即 : tM\equiv a_k-x_{k-1}\pmod{b_k}
  其中 : M,a_k,x_{k-1},b_k 都是已知的 。

  使用 exgcd 解出此同余方程 , 可以得到 t 的值 。

  将 t 的值代回 x_k = x_{k-1}+tM\ \ (t\in Z) ，就可得到x_k的值

  进行 k 次上述操作后 ，便可得到 方程组的解 。

• 附本题AC代码:

//扩展中国剩余定理模板题目 
//详见注释 
#include<cstdio>
using namespace std;
typedef long long ll;
ll n;
ll a[100010],b[100010]; 
ll mul(ll A,ll B,ll mod) //快速乘取余 模板
{
    ll ans=0;
    while(B>0)
      {
        if(B & 1) ans=(ans+A%mod)%mod;
        A=(A+A)%mod;
        B>>=1;
      }
    return ans;
}
ll exgcd(ll A,ll B,ll &x,ll &y) //扩展欧几里得 模板
{
    if(!B)
      {
        x=1,y=0;
        return A;
      }
    ll d=exgcd(B,A%B,x,y);
    ll tmp=x;
    x=y , y=tmp-A/B*y;
    return d;
}
ll lcm(ll A,ll B) //求最小公倍数
{
    ll xxx,yyy;
    ll g=exgcd(A,B,xxx,yyy);
    return (A/g*B);
}
ll excrt() //重点:求解同余方程组
{
    ll x,y;
    ll M=b[1],ans=a[1]; //赋初值 
    //M为前k-1个数的最小公倍数，ans为前k-1个方程的通解
    for(int i=2;i<=n;i++)
      {
        ll A=M,B=b[i];
        ll C=(a[i]-ans%B+B)%B; //代表同余方程 ax≡c(mod b) 中a,b,c

        ll g=exgcd(A,B,x,y);
        //求得A,B的最大公约数，与同余方程ax≡gcd(a,b)(mod b)的解，

        if(C%g) return -1; //无解的情况

        x=mul(x,C/g,B); //求得x的值,x即t 
        ans+=x*M;  //获得前k个方程的通解
        M=lcm(M,B); //更改M的值
        ans=(ans%M+M)%M;
      }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
      scanf("%lld%lld",&b[i],&a[i]);
    ll ans=excrt();
    printf("%lld",ans);
}