1048(得不到的爱情)证明

题意是给定两个数 $n,m(2\le n,m,\le 50000)n,m\; (2\backslash le\; n,m,\; \backslash le\; 50000)$n,m(2≤n,m,≤50000)​ ，$n,mn,m$n,m 互素，找到最大不能由若干个 $n,mn,m$n,m​​​ 组成的数。

首先插入一个前置知识

当 $kk$k​​ 可以由 $n,mn,m$n,m​​​ 组成时，可以用下面的式子来表示

而当 $k\ge n\times mk\; \backslash geq\; n\backslash times\; m$k≥n×m​ 时，$kk$k​ 等价于 $k-n\times mk-n\backslash times\; m$k−n×m​（相当于$k-n\times mk-n\backslash times\; m$k−n×m​ 加上 $nn$n​ 个 $mm$m​ 构成），所以这里只需讨论 $k\in [0,n\times m)k\; \backslash in[0,n\; \backslash times\; m)$k∈[0,n×m)​​​ 的情况，由（2）可得

由于 $n,mn,m$n,m​​​ 互素(即 $gcd(n,m)=1gcd(n,m)=1$gcd(n,m)=1​​​​ )，由（1）可得

假设最大不能被构成的数为 $tt$t​，由（2）（5）可得 $x,yx,y$x,y​ 至少必然有一者为负数，假设 $yy$y​ 为负数，想让最后的结果 $tt$t​ 尽量大，$yy$y​ 也要尽量大，最大的负数为 $-1-1$−1​ ，取 $yy$y​ 为 $-1-1$−1​​ ，由（3）化简

由于 $tt$t 要尽量大， $xx$x 应当取能取到的最大值 $m-1m-1$m−1 ，由(6)可得