题解 P4136 【谁能赢呢？】

· · 题解

一道数论的好题

n * n 的棋盘

如果n 为偶数 那么 {n^2} 也为偶数 此时除去开始的一个点 剩余 {n^2} - 1个点

如果{n^2} - 1 为奇数 推出 小明同学能赢

因为{n^2} - 1 & 1 != 0

设 {n^2} - 1 = 2 * k + 1

则前2k步一定以小红同学结束

第2k + 1步由小明同学走

小红同学就会开心惊奇的发现,他输了

反之 n为奇数

前 2 * {k_1}+ 1步由小明结束

第 2 * {k_1} + 2步小红下

这时,小明同学发现,他输了

由于 n 与 {n^2} 对于 模 2 同余

所以只考虑 n的奇偶情况

展示一段 神秘的代码

#include<cstdio>
main(int n) {while(scanf("%d", &n) && n) (n & 1) ? printf("Bob\n") : printf("Alice\n");}

只有两行？ 是的两行就够了

介绍一下 ? : 的使用 ?前一个判断式

值为真 执行?后语句

值为假 执行:后语句

n & 1 判断n的奇偶 把n 、1做与运算

即n的2进制形式 与1的2进制形式

若他们的同一位都为1 答案为1 否则为0

最短AC代码