蓝桥杯：买不到的数目

买不到的数目"/>

蓝桥杯：买不到的数目

对于两个互质的正整数 n , m n,m n,m,请找出来不能被 n n n和 m m m组成的最大数 X X X

例如:对于4,7那么 X X X=17，因为对于大于17的任一数都可由4和7组成。
重新翻译题目：
对于任一大于 X X X的正整数 Y Y Y满足 Y = a × n + b × m Y= a \times n+b \times m Y=a×n+b×m,其中 a ， b ∈ N a，b∈N a，b∈N.

不妨设 m < n m < n m<n，且 n ≡ r ( m o d m ) n≡r(mod\space m) n≡r(mod m)。

那么可知一个数如果可以被表示为 ( a × m ) + ( b × n ) (a\times m)+(b\times n) (a×m)+(b×n)的形式，则有 ( a × m ) + ( b × n ) ≡ b × r ( m o d m ) (a \times m)+(b \times n)≡b\times r(mod\space m) (a×m)+(b×n)≡b×r(mod m)。

此外，由于 m , n m,n m,n互质，由反证法易知0 , n , 2 n , 3 n , … ( m − 1 ) n ,n,2n,3n,\dots(m-1)n ,n,2n,3n,…(m−1)n对m的余数皆不相同。

所以按每个数对 m m m的余数进行划分。如果你想用 m m m和 n n n表示一个对 m m m的余数为 x x x的数，那么首先先要找一个最小的正整数 b b b使得 b × n ≡ x ( m o d m ) b\times n≡x(mod \space m) b×n≡x(mod m)，然后给他加上若干的m。

也就是说，在模m为x的所有数中，最小的能够用 m , n m,n m,n表示的数就是 b × n b\times n b×n，而最大的不能够被表示的数是 b × n − m b\times n-m b×n−m（如果 x x x是0，显然直接用 m m m就能表示，就不讨论了）所以最大的不能够表示的数是哪一个呢？
再把 b b b最大化成 m − 1 m- 1 m−1，就是 n ( m − 1 ) − m = m × n − n − m n(m-1) - m=m\times n - n -m n(m−1)−m=m×n−n−m了。