AcWing 1298. Solution to Cao Chong's pig raising problem

AcWing 1298 . Cao Chong raises pigs Answer key

Better reading experience

Title Description

Since Cao Chong got the elephant , Cao Cao began to think about letting his son do something , So he was sent to Zhongyuan pig farm to raise pigs , But Cao Chong was very unhappy , So in the work of careless , Once Cao Cao wanted to know the number of sows , So Cao Chong wanted to play with Cao Cao .

for instance , If there is $16$ A sow , If it's built $3$ A pigsty , be left over $1$ There's no place for a pig to settle down ; If you build $5$ A pigsty , But there is still $1$ A pig has no place to go ; If you build $7$ A pigsty , also $2$ The head has no place to go .

As Mr. Cao's personal secretary, you should report the accurate pig number to Mr. Cao , What are you gonna do? ？

Input format

The first line contains an integer $n$, Indicates the number of times to establish a pigsty ;

Next $n$ That's ok , Two integers per line $a_i,b_i$ Indicates that the $a_i$ A pigsty , Yes $b_i$ There's no place for a pig .

You can assume that $a_i,a_j$ Coprime

Output format

The output contains only one positive integer , That is, at least the number of pigs raised by Cao Chong

Data range

$1\le b\le 10$

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

all $a_i$ The product of does not exceed $10^{18}$

Answer key

The test point of this question is Chinese remainder theorem

We describe the Chinese surplus in the following form

Here we give the method of calculating Chinese Remainder Theorem and prove

1. Calculate the product of all modules $n$

2. For the first $i$ An equation ：

   a. Calculation $m_i=\frac{n}{n_i}$

   b. Calculation $m_i$ In the mold $n_i$ Inverse element in sense $m_i^{-1}$

   c. Calculation $c_i=m_i\times m_i^{-1}$ ( incorrect $n_i$ modulus )

3. The unique solution of the system of equations is ： $x={\sum }_{i=1}^k{a}_i{c}_i(mod{n}_i)$

prove :

We can prove the result obtained by this method $x$ For arbitrary $i=1,2,\dots ,k$ All meet $x\equiv a_i(mod{n}_i)$

When $i\ne j$ when , Yes
$$m_j\equiv 0(mod{n}_i)$$

For
$$c_j\equiv m_j\equiv 0(mod{n}_i)$$
According to
$$c_i=m_i\times m_i^{-1}\equiv 1(mod{n}_i)$$

For $x$ Yes
$$\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}$$
Obtain evidence

Find the inverse element in the sense of module

Then the idea of this topic becomes very clear , Now the question is how Find the inverse element in the sense of module

Let's look at a formula
$$a{a}^{-1}\equiv 1(modc)$$
Deformation can be obtained
$$a{a}^{-1}=kc+1$$
transposition
$$a{a}^{-1}-kc=1$$

It is observed that it is shaped like Euclidean equation
$$ax+by=c$$
Therefore, it can be solved by extended Euclidean

Complete code

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);// Output positive numbers 
    }
}