洛谷 P3951 小凯的疑惑(数学)

传送门:Problem P3951html

https://www.cnblogs.com/violet-acmer/p/9827010.htmlpost

参考资料:htm

  [1]:http://m.blog.sina.com.cn/s/blog_b046a49001015zun.html#page=1blog

题解:get

  两个互素的正整数a,b的非负线性组合ax+by不能表示的最大整数为 a*b-a-b;io

  证实:class

    例如a=5,b=6,则不能表示的最大整数为19,换言之全部大于19的整数均可以表示成ax+by,其中x,y为非负整数,好比20=5×4+6×0,21=5×3+6×1,22=5×2+6×2,...di

  推广到3个数的情形:已知1<a<b<c是给定的三个正整数,最大公约数为1,对于任意的非负整数x,y和z,ax+by+cz不能表示的最大整数是多少?
  根据前述的结论,这个最大整数不超过ab-a-b。
   部分结论:
    1)c>ab-a-b或ab-a-b-a<c<ab-a-b,不能表示的最大整数为ab-a-b;
    2)c=ab-a-b,不能表示的最大整数为ab-a-b-a;
    3)c=ab-a-b-a,不能表示的最大整数ab-a-b-min(2a,b); 这里min(p,q)返回p,q中的较小者。

  

转载于:https://www.cnblogs.com/violet-acmer/p/9827241.htmlvi