Day1 T1 小凯的疑惑 数论

你可以点击这个链接下载全部的AC代码

题目传送门 (LOJ)

题解

首先证明引理1 :对于互质的两个数,有任何大于 $a\times b$ 的数可以被 $a,b$ 表示出来

  • 由裴蜀定理可知 :对于 $(a, b) =1$ 不定方程 $ax+by=1$ 有整数解,
  • 所以任何大于 $a\times b$ 的数可以被 $a\times b +k\times ax+by$,即 $a\times b + c ,[ax+by=c]$ 所表示,
  • 至于小于$a\times b$的数不一定成立,是由于该不定方程的整数解有一数为
  • 对于 $a\times b$ ,我们可以将其理解为 $a$ 个 $b$ 或者 $b$ 个 $a$,令 $0\le x\le b$,
  • 对于 $ax+by=c$ 可以化成 $y = \frac{c-ax}{b}$
  • 又由于 $x \le b$ 所以 $y \ge \frac{c-ab}{b}$
  • 即$y\ge \frac{c}{b}-a$ , 由于c和b都是正数,所以$y \ge -a$ 引理得证

由于$(a, b)=1$的特殊性质,我们发现$a\times b -a$与$a\times b-b$都仅有一种构造方式,即(b-1)个a或者(a-1)个b,

我们用1式举例,发现由于它只有一种构造方式且这种构造中不含有 $b$,我们把它减一个b是定然不可以表示出来的,于是拿出本题答案 $a\times b – a – b$

但是,还需要证明 $(a\times b-a-b, a\times b]$ 中的所有数都可以表示出来,我们利用引理一

发现构造引理一中所述的数需要 $a$、$b$ 的系数均大于1,

我们考虑在$a\times b$之上的某些数减 $a$ 或减 $b$ 或减 $a+b$ ,即可构造出上区间中所有的数字,至此,答案可以被证明为 $a\times b – a- b$

当然有更好的证明方法,但是我是按自己所理解的相对好理解的一种方法叙述的。