usaco 4.1 Beef McNuggets 还有疑问的一题

如果有1,那么肯定无解

如果没有1,那么肯定存在解,但是不是无穷多个呢,容易注意到,如果所有数的最大公约数不是1,任意一个不能被这个最大公约数整除的数都可以成为解,就有无穷多个解

如果这n个数互质,假设有2个数m,n互质。可以把上限缩小到m*n-m-n,下面简单证明一下。设m>n

构造{m,2m....(n-1)*m}那么这个集合对n的余数,就等于{1,2,3,4..n-1},假设取集合中2个不同的元素有k1*m ≡ k2*m (mod n),因为(m,n)= 1,两边同乘m的逆元,就有k1 = k2。一个集合有n-1个元素,又是n的所有余数的子集。那么显然这2个集合相等。 因为m>n,可以再减去n,即 {m-n,2*m-n,...(n-1)*m-n},对于任意大于 n*m-m-n的数,我们都可以通过集合里跟他同余的数,构造出一组非负整数解。所以上限是这个。

我的疑问就在这里,如果两两都不互质,但3个数之间互质,又是怎样一种情况呢?我感觉无能为力,谁能给出解答??

我直接将上限设为256*256,ac了。

原文地址:https://www.cnblogs.com/1carus/p/3368857.html