这题之前就被灌输了“打表找规律”的思想，因此一直没有好好想这道题，过了一年还不太会qwq。虽然好像确实很简单，可是仍是带着感受会被嘲讽的心态写这个题解。。。并且还有一个log作法不会。。。html
法1：（一开始没看懂，后由hkk神仙教导ORZ）post
由于$ax+by=k$若是无视$\{x,y\}$非负整数解的条件的话，显然因为$gcd(a,b)=1$，因此全部$k$均可以表出。那么依题意若是有$k$不能够表出，是由于受了题目非负整数解条件的限制，也就是$x<0,y<0$，又由于$x,y$不可能同时$<0$，因此就是要求$x,y$异号表出的最大$k$。不妨让$a$项的$x$为负，那么为了保证$x,y$全部的通解都是一正一负，一定能够得出最后取模简化后必需要有$a\in (-b,0),b\in (0,a)$（由扩欧获得，不在这个范围也能够取模获得）。为了最大，$x$必须为$-1$，$b$项必须为$a-1$，这样就能够保证$k$最大了。spa
因此$k=-a+(a-1)b=ab-a-b$。code
法2：（同余类最短路）htm
有关同余类最短路我在这里写了一下，这里就不啰嗦了。而后根据这个原理，假设$a<b$，设$f[i]$表示$\min\{kb|kb\mod=i\}$，也就是最小能够用$b$的倍数表出的、模$a$余数为$i$的数。这个能够和套路同样建边跑最短路，最后按套路找$\max\{f[i]-a\}$就好了。可是这里数据规模很大。可是有一个特殊性质，$gcd(a,b)=1$，而且这个最短路实际就是从$f[0]$到$f[b\mod a]$到$f[2b\mod a]$，日后跑一条链......因此这个dis越跑越大，一直跑到$f[ab\mod a]=f[0]$发现无法松弛，终止。显然可证中间不会出现$f[kb\mod a]=f[0],k\in[1,a-1]$。那么能够直接得出结论在最后一次$f[(a-1)b\mod a]$的dis最大，所以答案就是$f[(a-1)b\mod a]-a=(a-1)b-a=ab-a-b$.
blog
a,b=map(int,input().split()) print(a*b-a-b)