题目
总共有$n$枚硬币均正面朝上,规则规定每次只能将其中$p$枚硬币翻面($1≤p≤n$)。问最少需要多少次操作才能将所有硬币翻面。
思路
- 先进行$n/p$次操作,将$(n/p - 1)*p$枚硬币翻面,令$r = n % p$,则剩余$r + p$;
- 考虑将其中$x$枚反面朝上的硬币翻面,$p - x$枚正面朝上的硬币翻面;
- 此时剩余正面向上的硬币总数为$x + r + p - (p - x) = p$,解方程得$x = (p - r) / 2$;
- 方程有解的前提是$x$为偶数,故$p$和$r$应同奇偶,如$p$为奇数,每做一次操作,正面向上的硬币总数变换奇偶性;
- 现在讨论$n$和$p$的奇偶关系:
- $n$为奇数,$p$为奇数:计$k$为$n/p$向上取整
- $k$为奇数,可行
- $k$为偶数,无解
- $n$为偶数,$p$为偶数:可行
- $n$为奇数,$p$为偶数:无解
- $n$为偶数,$p$为奇数:计$k$为$n/p$向上取整
- $k$为偶数,可行
- $k$为奇数,无解
- $n$为奇数,$p$为奇数:计$k$为$n/p$向上取整
- 应注意$n/p$介于1到2之间的情况。
答案
如满足上述奇偶讨论的要求:
- 当$n/p$介于1到2之间时,答案为3;
- 当$n/p$大于等于2时,答案为$n/p$向上取整;
不满足则无解。