【牛客多校】Han Xin and His Troops

题目：

His majesty chatted with Han Xin about the capabilities of the generals. Each had their shortcomings. His majesty asked, ``How many troops could I lead?" Han Xin replied, ``Your highness should not lead more than 100000." His majesty said, ``And what about you?" ``For your humble servant, the more the merrier!" said Han Xin.

---Records of the Grand Historian

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.

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

示例1

输入

输出

示例2

输入

输出

he was definitely lying

示例3

输入

2 10
11 3
19 7

输出

he was probably lying


题目大意：韩信点兵，给你n个结果，兵队总数%ai=bi，然后求出最后兵队最少到底有多少人。
        如果这个数不存在，输出he was definitely lying
       如果数量大于给定的门槛m，输出he was probably lying，否则出输出人数。
题解：因为最后的余数并不是完全互质，所以需要使用扩展中国剩余定理。
     还有一个坑，就是这些余数可能完全互质，所以最后的M会特别特别大，
     我之前使用的是洛谷中国剩余定理模板题的第一个模板，就是因为M特别大，
     改写成了java，用大数做就过了。写的有点丑，不要介意。

import java.util.*;
import java.math.*;
import java.security.MessageDigest;
 
public class Main {
    static int n;
    static BigInteger m,x,y;
    static BigInteger[] ai=new BigInteger[200];
    static BigInteger[] bi=new BigInteger[200];
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        m=cin.nextBigInteger();
        for(int i=1;i<=n;i++)
        {
            bi[i]=cin.nextBigInteger();
            ai[i]=cin.nextBigInteger();
        }
        BigInteger ans = excrt();
        long flag=-1;
        if (ans.compareTo(BigInteger.valueOf(flag))==0)
                System.out.print("he was definitely lying
");
        else if(ans.compareTo(m)!=-1&&ans.compareTo(m)!=0)
            System.out.print("he was probably lying
");
        else System.out.print(ans);
    }
     
    public static BigInteger excrt()
    {
        BigInteger k;
        BigInteger ans = ai[1];
        BigInteger M=bi[1];
        for (int i = 2; i <= n; i++)
        {
            BigInteger a = M, b = bi[i];
            BigInteger c=ai[i].subtract(ans.mod(b)).add(b).mod(b);
            BigInteger gcd = exgcd(a, b), bg = b .divide(gcd);
            long flag=-1;
            if (c.mod(gcd).compareTo(BigInteger.ZERO)!=0) return BigInteger.valueOf(flag);
      
            x = mul(x,c.divide(gcd), bg);
            ans=ans.add(x.multiply(M));
            M =M.multiply(bg);
            ans = (ans.mod(M).add(M)).mod(M);
        }
        return (ans.mod(M).add(M)).mod(M);
    }
     
    public static BigInteger mul(BigInteger a, BigInteger b, BigInteger mod)
    {
        BigInteger res = BigInteger.ZERO;
        while (b.compareTo(BigInteger.ZERO)>0)
        {
            if (b.mod(BigInteger.valueOf((long)2)).compareTo(BigInteger.ZERO)>0) res = res.add(a).mod(mod);
            a = a.add(a).mod(mod);
            b = b.divide(BigInteger.valueOf((long)2));
        }
        return res;
    }
      
    public static BigInteger exgcd(BigInteger a, BigInteger b)
    {
        if (b.compareTo(BigInteger.ZERO)==0)
        {
            x = BigInteger.ONE; y = BigInteger.ZERO;
            return a;
        }
        BigInteger gcd = exgcd(b, a.mod(b));
        BigInteger tp = x;
        x = y; y = tp.subtract(a.divide(b).multiply(y));
        return gcd;
    }
}

贴一下洛谷模板题：https://www.luogu.org/problem/P4777

模板来源：https://blog.csdn.net/niiick/article/details/80229217

C++模板代码：

//niiick
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=100010;
int n;
lt ai[maxn],bi[maxn];

lt mul(lt a,lt b,lt mod)
{
    lt res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

lt exgcd(lt a,lt b,lt &x,lt &y)
{
    if(b==0){x=1;y=0;return a;}
    lt gcd=exgcd(b,a%b,x,y);
    lt tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}

lt excrt()
{
    lt x,y,k;
    lt M=bi[1],ans=ai[1];//第一个方程的解特判
    for(int i=2;i<=n;i++)
    {
        lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
        lt gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1; //判断是否无解，然而这题其实不用

        x=mul(x,c/gcd,bg);
        ans+=x*M;//更新前k个方程组的答案
        M*=bg;//M为前k个m的lcm
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    bi[i]=read(),ai[i]=read();
    printf("%lld",excrt());
    return 0;
}

View Code