Who is better?

徐州网络赛A

所谓斐波那契博弈

考场推了个假规律自闭==

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
        static BigInteger m[]=new BigInteger[15];
        static BigInteger c[]=new BigInteger[15];
        static int  n;
        static BigInteger _m;
        static BigInteger x,y;
        static long A[]=new long[400000];
        static int cnt=0;
        static void init()
        {
            A[0]=1;
            A[1]=1;
            for(cnt=2;;cnt++){
                A[cnt]=A[cnt-1]+A[cnt-2];
                if(A[cnt]>1e15){
                    break;
                }
            }
        }
        public  static BigInteger[] ex_gcd(BigInteger a,BigInteger b){ 
            BigInteger ans; 
            BigInteger[] result=new BigInteger[3]; 
            if(b.equals(BigInteger.ZERO)) 
            { 
                result[0]=a; 
                result[1]=BigInteger.ONE; 
                result[2]=BigInteger.ZERO; 
                return result; 
            } 
            BigInteger [] temp=ex_gcd(b,a.mod(b)); 
            ans = temp[0]; 
            result[0]=ans; 
            result[1]=temp[2]; 
            result[2]=temp[1].subtract((a.divide(b)).multiply(temp[2]));
            //System.out.println(result[0]+" "+result[1]+" "+result[2]);
            return result; 
        }
        static BigInteger getInv(BigInteger a,BigInteger md)
        {
            //x=BigInteger.ZERO;y=BigInteger.ZERO;
            BigInteger d[]=ex_gcd(a,md);
            //System.out.println(a+" "+md);
            //System.out.println(x+" "+y);
            //System.out.println(d[1]);
            return (d[0].equals(BigInteger.ONE))?(d[1].add(md)).mod(md):BigInteger.valueOf(-1);
        }
        static BigInteger exCRT(int n)
        {
            BigInteger m1,m2,c1,c2,d;
            for(int i=2;i<=n;i++)
            {
                m1=m[i-1];m2=m[i];c1=c[i-1];c2=c[i];
                d=m1.gcd(m2);
                if(!(c2.subtract(c1)).mod(d).equals(BigInteger.ZERO))return BigInteger.valueOf(-1);//此时无法合并
                m[i] = m[i-1] .multiply(m[i]).divide(d) ;
                BigInteger t=(c2.subtract(c1)).divide(d);
                //System.out.println(t);
                c[i] = t.multiply( getInv(m1.divide(d),m2.divide(d))) .mod ( m2.divide(d) ).multiply(m1) .add(c1) ;
                //System.out.println(c[i]);
               // System.out.println(getInv(m1.divide(d),m2.divide(d)));
                c[i] = ( (c[i] .mod(m[i])) .add(m[i]) ) .mod( m[i]);
               // System.out.println(m[i]);
            }
            return c[n];
        }
     public static void main(String[] args) {
           init();
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
           // int k=0;
            for(int i=1;i<=n;i++){
                m[i]=sc.nextBigInteger();
                c[i]=sc.nextBigInteger();
 
            }
 
            BigInteger ans=exCRT(n);
         
           
           long N=ans.longValue();
           if(N==-1){
               System.out.println("Tankernb!");
               return ;
           }
        /*  if(N==0){
               BigInteger t=m[1],a=BigInteger.ONE;
               for(int i=1;i<=n;i++){
                   t=m[i].gcd(t);
                   a=a.multiply(m[i]);
               }
               a=a.divide(t);
               N=a.longValue();
           }*/
           if(N<=3){
               System.out.println("Lbnb!");
               return;
           }
           if(N==4){
               System.out.println("Zgxnb!");
               return ;
           }
          if(N==5){
               System.out.println("Lbnb!");
               return;
          }
         for(int i=0;i<=cnt;i++){
             if(A[i]==N){
                 System.out.println("Lbnb!");
               return;
             }
         }
           System.out.println("Zgxnb!");
           
           
 
        }
 
}
原文地址:https://www.cnblogs.com/liulex/p/11482257.html