洛谷P3951 小凯的疑惑 - 数学 /扩展欧几里得

传送门

题意：求出a和b不能通过线性组合（即n*a+m*b）得到的最大值；

思路：摘自洛谷；

　不妨设 a<b

　假设答案为 x

　若

　　x≡m*a ( mod b )(1≤m≤b−1)

*注：　　　　　1+3m＝（mod3）什么意思？

　　　　　　　　【答】：

　　　　　　　　　　后面的 mod 3 表示：相对于  的模，即用  来除，得到相应的余数

　　　　　　　　　　举例来说，+3m＝（mod3），+3m 用  来除 的余数是 

　即

　　x=m*a+n*b (1≤m≤b−1)

显然当n≥0 时 x 可以用 a,b 表示出来，不合题意。

因此当 n = -1 时 x 取得最大值，此时 x=m*a−b 。

显然当 m 取得最大值b−1 时 x 最大，此时 x = (b−1) *a − b= a*b−a−b

因此 a,b 所表示不出的最大的数是a*b−a−b

#include <iostream>

using namespace std;

typedef long long ll;

int main(){

    ll a,b;

    cin>>a>>b;

    cout<<a*b-a-b<<endl;

}