UVA 847 - A Multiplication Game

题目链接

题意：一个数一开始是1，每次轮流乘2-9，谁先大于n谁就赢，问谁胜

思路：博弈，找出必胜态，2-9为stan，10-18为ollie,19-162为stan...发现都是乘2乘9交替

代码：

#include 
  
   
#include 
   
     #include 
    
      long long n; bool judge(long long n) { long long a = 1, b = 1; int flag = 1; while (1) { if (flag) { a = b + 1; b *= 9; if (a <= n && n <= b) return true; flag = 0; } else { a = b + 1; b *= 2; if (a <= n && n <= b) return false; flag = 1; } } } int main() { while (~scanf("%lld", &n)) { printf("%s wins.\n", judge(n)?"Stan":"Ollie"); } return 0; }