http://poj.org/problem?id=3372

打表后就看出模式了。。(时才YES)

但是还是要证一下,不证不舒服,嗯。

我们要证明的是:

必要性:
首先我们解释下为什么当时,有的孩子分不到糖果。(“为什么有的孩子分配不到糖果!凶手就是——数学!”)
因为,则N必有一奇素因子p。
将方程变形,得

因为p是N的一个因子,所以同时也有

因为p为奇素数,所以p必有非二次剩余(证明如下图),所以可以找到一个使方程无解的a,即有的孩子分配不到糖果。

首先定义非二次剩余是什么:


然后是证明:(补充下为什么不可能:因为,所以只能当时同余式成立,这显然不可能)

充分性:
然后我们看看为什么当时,所有的孩子都分到了糖果。
反证,假设存在

也就是在这N次分配时,有两次分配给了同一个孩子,所以必有一个孩子分不到糖果。
将上式变形为

由于必定一奇一偶,而N只有一素因子2,所以同余式不成立,即不存在两次分配给了同一个孩子,矛盾,故充分性得证。

综上,原命题成立。

Comments

comments powered by Disqus