NYOJ 788 又见Alice and Bob

题目链接~~>

                    一看见类似博弈的就不想做（但是这题和博弈没关系！！）。。。。

解题思路： 给一个原始集合，每次操作都会往集合中加入一个新的元素，找出最后集合中元素的个数total，然后用 total-n 就是新加进去的元素个数。判断total-n 的奇偶性就可以判断出谁赢了。如何求total呢？如果开始时集合中只有2个数6  27，通过这两个数可以加进集合的数有21  15  9  3，这个过程实际上就是求gcd（6,27）的过程，最小的数就是gcd(6,27)=3,还发现集合中的元素都是3的倍数，那我们只需要判断[1,27]之间3的倍数有多少个就行了。   解法：求出n个数中的最大值Max和这n个数的最大公约数p，判断（Max / p — n）的  奇偶性即可。奇数Alice赢（因为集合中的数都是最大公约数的倍数，且不超过最大值，总个数就是最大数除以最大公约数）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int g[120] ;
     
    
   

    

     

    
    

     

      int gcd(int x,int y) // 求公约数
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int t ;
     
    
   

    

     

    
    

     
 while(y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       t=x%y ;
     
    
   

    

     

    
    

     

       x=y ;
     
    
   

    

     

    
    

     

       y=t ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,n,max,x,num ;
     
    
   

    

     

    
    

     
 while(scanf("%d",&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       max=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&g[i]) ;
     
    
   

    

     

    
    

     

       max=max < g[i] ? g[i] : max ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       x=g[0] ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<n ;i++)
     
    
   

    

     

    
    

     

       x=gcd(x,g[i]) ;
     
    
   

    

     

    
    

     

       num=max/x-n ;
     
    
   

    

     

    
    

     
 printf("%s\n",num&1 ? "Alice" : "Bob") ; // 三目运算符很好用
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/15500599