算法1
(数论数学) $O(1)$
那么实际上就是求a b均为正整数且互质时,ax+by 所不能表示的最大正整数(x,y>=0)
关键1
由无解想到有解
设ax+by 所不能表示的最大正整数(x,y>=0)为k
ax+by=k
定有整数解
证明:
k%gcd(a,b)=k%1=0
所以定有整数解
但是没有非负整数解
而x y都小于0时k也小于0,不行
x<0 y=0 || x=0 y<0也不行
只有(x<0 &&y>0)||(x>0&&y<0)
那么大于k的整数一定能被ax+by表示
设ax+by=k+a
此时x和y是这个不定方程的非负整数解
a(x-1)+by=k
y>=0
故x-1<0
x<1
0<=x<1
x=0
k=-a+by
关键2
把不定方程通解的性质运用到特解里
既然y无法确定取值
那么干脆设y=a+f
f为整数
a+f>=0
f>=-a
k=-a+b(a+f)
=-a+ab+bf
=a(b-1)+bf
b>=1
所以b-1>=0
所以f<0
所以f<=-1
关键3
运用函数单调性
a(b-1)>=0
b>0
是单调递增
f=-1时k最大
k=ab-a-b
合法性:
-a<=f<=-1
a>=1
-a<=-1
合法
故答案为ab-a-b
注意longlong
时间复杂度
$O(1)$
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
long long a ,b;
cin>>a>>b;
cout<<(a*b-a-b)<<endl;
return 0;
}