C. Alice, Bob, Oranges and Apples

最新推荐文章于 2025-04-17 11:42:57 发布

ao9795

最新推荐文章于 2025-04-17 11:42:57 发布

阅读量234

点赞数

原文链接：http://www.cnblogs.com/towerbird/p/11238401.html

版权

http://codeforces.com/problemset/problem/585/C

1、不要把橘子和苹果分开看，都看数字1，就不难发现alice和bob手里最后的数就是x和y ，这个过程就很明显是辗转相减了，重复的辗转相减凑一块就是辗转相除了。

2、要游戏能成功，只要最后有gcc（1，1），即gcc（x，y）==1即可。

 1 public class Main {
 2     static final int maxn = 4100;
 3     static int n;
 4     static ArrayList<Long>al=new ArrayList<>();
 5 
 6     public static void main(String[] args) {
 7         IO io=new IO();
 8         long x=io.nextLong(),y=io.nextLong();
 9         if (gcd(Math.max(x,y),Math.min(x,y))!=1)io.println("Impossible");
10         else {
11             int v=x<y?1:0;
12             //最后一步里除数是1，余数是0，alice或bob手里要拿一个1，这个1从除数里匀一个出来
13             long last=al.remove(al.size()-1)-1;al.add(last);
14             for (int i=0;i<al.size();i++,v^=1)io.print(al.get(i)+""+(char)('A'+v));
15         }
16         io.println("");
17     }
18 
19     static long gcd(long a,long b){
20         if (b==0)return a;
21         al.add(a/b);
22         return gcd(b,a%b);
23     }
24 
25     
26 }