题意:三堆石子,每次能拿走斐波那契数个石子,先取完石子胜,问先手胜还是后手胜 石子个数<=1000 多组数据
题目链接:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 const int MAXN = 2333;11 int n, m, p, lx;12 int f[MAXN], sg[MAXN];13 bool tf[MAXN];14 15 template void read (tn & a) {16 tn x = 0, f = 1;17 char c = getchar();18 while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar(); }19 while (c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); }20 a = f == 1 ? x : -x;21 }22 23 int get_f() {24 f[0] = 0;25 f[1] = 1;26 f[2] = 2;27 int i;28 for (i = 3; f[i - 1] <= 1100; ++i) f[i] = f[i - 1] + f[i - 2];29 return i - 1;30 }31 32 void get_() {33 sg[0] = 0;34 sg[1] = 1;35 for (int i = 2; i <= 1100; ++i) {36 for (int j = 0; j <= 1100; ++j) tf[j] = 1;37 for (int j = 1; j <= lx && f[j] <= i; ++j) {38 tf[sg[i - f[j]]] = 0;39 }40 int j = 0;41 while (!tf[j] && j <= 1100) ++j;42 sg[i] = j;43 }44 }45 46 int main() {47 lx = get_f();48 get_();49 read(n);50 read(m);51 read(p);52 while (n != 0 || m != 0 || p != 0) {53 if (sg[n] ^ sg[m] ^ sg[p]) printf("Fibo\n"); else printf("Nacci\n"); 54 read(n);55 read(m);56 read(p);57 }58 return 0;59 }