定理描述:
第一鸽巢原理:
- 把多于 m × n + 1 ( n 不 为 0 ) m\times n+1(n不为 0) m×n+1(n不为0)个的物体放到 n n n 个抽屉里,则至少有一个抽屉里有不少于 m + 1 m+1 m+1的物体
- 把 n − 1 n-1 n−1件东西放入 n n n个抽屉,则至少一个抽屉是空的。
- 无穷多的东西放到有限的抽屉里,至少一个抽屉有无数个东西。
第二鸽巢原理:
1.把
m
×
n
-
1
m\times n-1
m×n-1个物体放入
n
n
n个抽屉中,其中必有一个抽屉中至多有
m
−
1
m-1
m−1个物体。
一些结论:
1.
n
+
1
n+1
n+1个互不相同的正整数,它们全都小于或等于
2
n
2n
2n,证明当中一定有两个数是连续的。
2.
m
m
m个在模
m
m
m意义下不同的正整数可以构成模
m
m
m的完全剩余系。
3.
n
n
n个数(
n
>
m
n > m
n>m),必然可以找到两个
4.
m
m
m个互不相同的数,一定能找到若干连续的数,使他们之和模
m
m
m为
0
0
0
题目:
Flowers ( 2019-ICPC沈阳 - L )
题解: