普及一下初等数论知识。

首先设 $x,y$ 为公鸡、母鸡的数量，则 $100-x-y$ 为小鸡的数量。我们有二元一次方程：

而题目即要我们求出它所有满足 $x,y,100-x-y\ge 0$ 的解。

$\mathcal{O}\left(n^2\right)$ 枚举太不牛了，像是原始社会人类的做法。本文将介绍一种古希腊时代的做法。

扩展欧几里得算法

前置知识：辗转相除法。

对于一个一般的二元一次方程：

其有 整数 解的充要条件是 $c\bmod \gcd(a,b)=0$。

必要性显然，因为左边一定是 $\gcd(a,b)$ 的整数倍。考虑证明充分性。

此时原方程的解和 $ax+by=\gcd(a,b)$ 的解一一对应。我们考虑证明这个方程一定有整数解。

回顾辗转相除法中的二元组序列 $(a_i,b_i)$，把 $x,y$ 的系数当成这个二元组序列中的第一项。记 $k$ 表示最小的 $k$ 使得 $b_k=0$。此时会满足 $a_k=\gcd(a_1,b_1)$。

特解

记 $(x_i,y_i)$ 表示 $a_ix+b_iy=\gcd(a_i,b_i)$ 的任意一组解。则 $(x_k,y_k)=(1,0)$。否则 $(x_i,y_i)$ 可以通过 $(x_{i+1},y_{i+1})$ 推出。

辗转相除保证了每一个二元组中的两数最大公约数相等。下文记 $g$ 为所有二元组的 $\gcd(a_i,b_i)$。

具体如下：

首先我们有 $a_{i+1}x_{i+1}+b_{i+1}y_{i+1}=g$。

代入 $a_{i+1},b_{i+1}$ 得到：

$$b_ix_{i+1}+(a_i\bmod b_i)y_{i+1}=g$$

把 $\bmod$ 写成一般形式，得到：

$$b_ix_{i+1}+\left(a_i-b_i\left\lfloor\dfrac{a_i}{b_i}\right\rfloor\right)y_{i+1}=g $$

整理得：

$$a_iy_{i+1}+b_i\left(x_{i+1}-\left\lfloor\dfrac{a_i}{b_i}\right\rfloor y_{i+1}\right)=g $$

令 $x_i=y_{i+1}$，$y_i=x_{i+1}-\left\lfloor\dfrac{a_i}{b_i}\right\rfloor y_{i+1}$ 即可。

于是我们通过 $(x_{i+1},y_{i+1})$ 推出了一组可行的 $(x_i,y_i)$。

求特解的过程就是在辗转相除时顺带求 $(x_i,y_i)$，递归的层数仍然是 $k$，因此时间复杂度为 $\mathcal{O}(\log n)$。

通解

我们得到一组 $(x_1,y_1)$ 后，扩大 $\dfrac{c}{g}$ 倍，得到 $ax+by=c$ 的一组特解。

我们先认为 $a,b$ 均为正值，因为可以通过调节解前面的符做到这一点，且得到的新方程和原方程的解一一对应。

至于通解，考虑将 $x$ 加上一个偏移量 $\Delta x$，$y$ 相应减去一个偏移量 $\Delta y$。在此基础上希望偏移量尽量小。则：

注意到 $ax+by=c$，那么两边同时减去 $c$ 得 $a\Delta x=b\Delta y$。

记 $a=pg,b=qg$，两边同时除以 $g$ 得 $p\Delta x=q\Delta y$。那么令 $\Delta x=q,\Delta y=p$ 即可得到一组极小的偏移量。

如何证明她是最小的？假设最小的偏移量 $x',y'$ 满足 $px'=qy'$ 且 $x'<\Delta x$，$y'< \Delta y$，将两式相除得 $\dfrac{q}{x'}=\dfrac{p}{y'}$。记这个比值为 $\dfrac{s}{t}$，且 $\gcd(s,t) = 1$。则有 $q=\dfrac{sx'}{t},p=\dfrac{sy'}{t}$。

此时还需要一个引理：

$\bold{Lemma\space 1}$

若 $ab\bmod p=0$，$\gcd(a,p)=1$，则 $b\bmod p = 0$。

$\bold{Proof}$

$p=1$ 时显然，否则根据扩展欧几里得算法可以得出一定存在整数对 $(x,y)$ 使得 $ax+by=1$。那么 $b=(ax+py)b=xab+byp$。由于 $xab$ 和 $byp$ 都是 $p$ 的倍数，所以 $b\bmod p =0$。

$\mathcal{Q.E.D.}$

那么根据引理 $t$为 $x',y'$ 的公约数。而由于 $x',y'$ 是最小的偏移量，她们一定互质，否则可以通过除以最大公约数得到一组更小的偏移量。因此 $t=1$。那么 $q=sx',p=sy'$。而 $s$ 为正整数，会导出 $x'\ge \Delta x$，$y'\ge \Delta y$。矛盾。

因此 $q,p$ 就是一组最小的偏移量。

记一开始的特解为 $(x_0,y_0)$，那么通解的公式就是 $\left(x_0+\dfrac{kb}{g},y_0+\dfrac{ka}{g}\right),k\in \mathbb{Z}$。注意我们之前做了一些一一对应工作，可能还要将解映射回原方程。

这样得到的 $(x,y)$ 一定是解，且一定不会遗漏掉任何一个解。可以假设遗漏掉的解，然后找到最接近她的通解，从而导出更小的偏移量，与已知条件矛盾。

有通解公式还不够，我们需要找到满足 $x,y,100-x-y$ 均为正整数的解。此时相当于给 $k$ 加了一个取值范围，容易二分求出这个取值范围。

那么就可以做到在 $\mathcal{O}(\log n)$ 时间内求出解的个数 $w$。如果仅仅到这一步，可以明显体现出扩展欧几里得算法的优势。但是在要求输出所有解的情况下，时间复杂度会变为 $\mathcal{O}(\log n+w)$。而最坏情况下 $w=\mathcal{O}\left(n^2\right)$。因此在此情形下和暴力没有本质区别。不过处理一些 $w\ll \mathcal{O}\left(n^2\right)$ 的问题（譬如本题）时还是能够体现其优势。