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

传送门html

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

思路：摘自洛谷；post

　不妨设 a<bspa

　假设答案为 x
code

　若htm

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

*注：　　　　　1+3m＝1（mod3）什么意思？
　　　　　　　　【答】：
　　　　　　　　　　后面的 mod 3 表示：相对于 3 的模，即用 3 来除，获得相应的余数
　　　　　　　　　　举例来讲，1+3m＝1（mod3），1+3m 用 3 来除 的余数是 1

 

　即ci

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

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

所以当 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;
}