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 ,我们可以将其理解为 ab 或者 ba,令 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 -aa\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] 中的所有数都可以表示出来,我们利用引理一

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

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

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