徐州网络赛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!"); } }

最新文章

  1. 使用NUnit为游戏项目编写高质量单元测试的思考
  2. GIT分布式版本控制系统
  3. Python 进程间通信
  4. excel表格中如何将内容粘贴到筛选后的可见单元格[转]
  5. excel查看VBA代码快捷键
  6. hive安装--设置mysql为远端metastore
  7. 移动开发流量省起来之Zepto
  8. 一种比较少见的C#代码段
  9. Burnside引理和polay计数学习小记
  10. 【ADO.NET】3、从TXT中导入数据到数据库
  11. 轻松学习之Linux教程一 ubuntu14.04+windows双系统安装
  12. 导入导出Mysql数据库、表结构、表数据
  13. Visual Studio 2017 Enterprise 发布 15.3.3 版,附离线安装包百度网盘下载。
  14. Nerd的畅销产品
  15. 咏南WEB APP开发框架
  16. [Leetcode]394.字符串解码
  17. SVN 安装vs插件
  18. centos6.5重新调整/home和跟目录/大小
  19. Docker学习笔记之搭建Docker运行环境
  20. Python源码文件中带有中文时,输出乱码

热门文章

  1. [转帖]Linux网络管理员不得不了解的系统目录/proc/sys/net/(网络配置)
  2. 【转帖】AMD:未向合资企业THATIC发放后续芯片设计授权
  3. [HAOI2018]苹果树题解
  4. MD5算法+盐Salt
  5. [..net core]4.入口,Main方法 及InProcess
  6. NlData初学者开发篇(ORM)
  7. vue项目进行时,script标签中,methods事件中函数使用的async/await
  8. 缓存机制总结(JVM内置缓存机制,MyBatis和Hibernate缓存机制,Redis缓存)
  9. java面试题全集(上)
  10. TCP Retransmission 连接超时