2019牛客暑假多校第十场 D——Han Xin and His Troops(拓展中国剩余定理)

2019牛客暑假多校第十场 D——Han Xin and His Troops(拓展中国剩余定理)

链接：https://ac.nowcoder.com/acm/contest/890/D
来源：牛客网

Han Xin was a military general who served Liu Bang during the Chu-Han contention and contributed greatly to the founding of the Han dynasty. Your friend, in a strange coincidence, also named Han Xin, is a military general as well.

One day you asked him how many troops he led. He was reluctant to tell you the exact number, but he told you some clues in certain form, for example:

• if we count the troops by threes, we have two left over;
• if we count by fives, we have three left over;
• if we count by sevens, two are left over;
• …
  You wonder the number of his troops, or he was simply lying. More specifically, you would like to know the minimum possible number of troops he leads, and if the minimum number is too large, then you suspect he was lying.

输入描述:
The first line of input contains two integers n, m (1 \leq n \leq 100, 1 \leq m \leq 10^{18})(1≤n≤100,1≤m≤10
18
), the number of clues he told you and the threshold that you think he was probably lying.

The remaining part of the input are n lines, specifying the clues, Each line consists of two integers a, b (0 \leq b < a < 10^5)(0≤b<a<10
5
), representing a clue that b troops are left over if we count them by a’s.
输出描述:
If there does not exist a non-negative number of troops satisfying all clues, print \texttt{he was definitely lying}he was definitely lying; otherwise, if the minimum non-negative possible number of troops is greater than m, print \texttt{he was probably lying}he was probably lying; otherwise, print the minimum non-negative number.
示例1
输入
复制
3 100
3 2
5 3
7 2
输出
复制
23
示例2
输入
复制
4 10000
12 7
15 2
30 5
8 6
输出
复制
he was definitely lying
示例3
输入
复制
2 10
11 3
19 7
输出
复制
he was probably lying

题目大意：

韩信点兵
给个n，m
接下来n行，每行两个数，一个a一个 b. 士兵的数量%a == b
(并不保证b一定时质数)

解题思路：

明显的中国剩余定理，但是b不是质数，所以时拓展的中国剩余定理
这个题最坑的就是说在运算中的数有超过long long 的
如果用C++就要用__int128或者 大数的模板写。
也可用java的大数写。

AC代码:

import java.util.Scanner;
import java.math.*;
 
public class Main {
    static BigInteger m[],a[];
    static BigInteger MM;
    static int n;
 
    static void init(){
        m = new BigInteger[200];
        a = new BigInteger[200];
    }
 
    static BigInteger exgcd(BigInteger a,BigInteger b,BigInteger x[],BigInteger y[]){
        if(b.compareTo(BigInteger.ZERO) == 0){
            x[0] = BigInteger.ONE;
            y[0] = BigInteger.ZERO;
            return a;
        }
        BigInteger re = exgcd(b,a.mod(b),x,y);
        BigInteger tmp = x[0];
        x[0] = y[0];
        y[0] = tmp.subtract((a.divide(b)).multiply(y[0]));
        return re;
    }
 
    static BigInteger work(){
        BigInteger M = m[1];
        BigInteger A = a[1];
        BigInteger t,d,x[] = {BigInteger.ZERO},y[] = {BigInteger.ZERO};
        for(int i = 2;i<=n;i++){
            d = exgcd(M,m[i],x,y);
            if(((a[i].subtract(A)).mod(d)).compareTo(BigInteger.ZERO)!=0){
                return BigInteger.ZERO.subtract(BigInteger.ONE);
            }
            x[0] = x[0].multiply(a[i].subtract(A).divide(d));
            t = m[i].divide(d);
            x[0] = x[0].mod(t).add(t).mod(t);
            A = M.multiply(x[0]).add(A);
            M = M.divide(d).multiply(m[i]);
            A = A.mod(M);
        }
        A = A.mod(M).add(M).mod(M);
        return A;
    }
 
    static public void main(String []args){
        init();
        Scanner cin = new Scanner(System.in);
        String sMM;
        n = cin.nextInt();
        MM = cin.nextBigInteger();
        for(int i = 1;i<=n;i++){
            m[i] = cin.nextBigInteger();
            a[i] = cin.nextBigInteger();
        }
        BigInteger res = work();
        if(res.compareTo(BigInteger.ZERO.subtract(BigInteger.ONE)) == 0){
            System.out.println("he was definitely lying");
        }else if(res.compareTo(MM)>0){
            System.out.println("he was probably lying");
        }else{
            System.out.println(res.toString());
        }
    }
}