AcWing 1298 .曹冲养猪 题解

更好的阅读体验

题目描述

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。

举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了；如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去；如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。

你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 $n$，表示建立猪圈的次数；

接下来 $n$ 行，每行两个整数 $a_i,b_i$表示建立了 $a_i$ 个猪圈，有 $b_i$ 头猪没有去处。

你可以假定 $a_i,a_j$ 互质

输出格式

输出仅包含一个正整数，即为曹冲至少养猪的数目

数据范围

$1\le b\le 10$

$1\le b_i\le a_i\le 1100000$

所有$a_i$的乘积不超过$10^{18}$

题解

这道题的考点是中国剩余定理

我们将中国剩余描述为如下形式

在这里给出计算中国剩余定理的方法并证明

1. 计算所有模数的积$n$

2. 对于第 $i$ 个方程：

   a. 计算 $m_i=\frac{n}{n_i}$

   b. 计算 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$

   c. 计算 $c_i=m_i\times m_i^{-1}$ (不对 $n_i$ 取模)

3. 方程组的唯一解为： $x={\sum }_{i=1}^k{a}_i{c}_i(mod{n}_i)$

证明:

我们可以证明用这种方法得到的 $x$ 对于任意的$i=1,2,\dots ,k$ 均满足$x\equiv a_i(mod{n}_i)$

当$i\ne j$ 时，有
$$m_j\equiv 0(mod{n}_i)$$

则对于
$$c_j\equiv m_j\equiv 0(mod{n}_i)$$
又根据
$$c_i=m_i\times m_i^{-1}\equiv 1(mod{n}_i)$$

则对于 $x$ 有
$$\begin{gathered} x\equiv \sum _{j=1}^k{a}_j{c}_j(mod{n}_i) \\ \equiv a_i{c}_i(mod{n}_i) \\ \equiv a_i\times 1(mod{n}_i) \\ \equiv a_i(mod{n}_i) \end{gathered}$$
得证

求模意义下的逆元

则本题的思路变得很清晰，现在问题来到如何求模意义下的逆元

我们来看一个式子
$$a{a}^{-1}\equiv 1(modc)$$
变形可得
$$a{a}^{-1}=kc+1$$
移项
$$a{a}^{-1}-kc=1$$

观察发现形如欧几里得方程
$$ax+by=c$$
故可用扩展欧几里得求解

完整代码

import java.io.*;
import java.util.*;
class Main
{
    
    static long sum=1;
    static int n;
    static int[] a=new int[10];
    static int[] c=new int[10];
    static long x;
    static long y;
    static long res=0;
    public static long exgcd(long a,long b)
    {
    
        if(b==0)
        {
    
            x=1;
            y=0;
            return a;
        }
        long d=exgcd(b,a%b);
        long tmp=x;
        x=y;
        y=tmp-(a/b)*x;
        return d;
    }
    public static void main(String[] agrs)throws IOException
    {
    
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine());
        for(int i=0;i<n;i++)
        {
    
            String[] param=reader.readLine().split(" ");
            c[i]=Integer.parseInt(param[0]);
            a[i]=Integer.parseInt(param[1]);
            sum*=c[i];
        }
        for(int i=0;i<n;i++)
        {
    
            long m=sum/c[i];
            long re=exgcd(m,c[i]);
            res=(res+a[i]*m*x%sum)%sum;
        }
        System.out.println((res%sum+sum)%sum);//输出正数
    }
}