数论极菜的小萌新我刚看这题时看不懂exgcd做法的题解，后来在网上找到了一篇博客，感觉代码和推导都更加清新易懂，于是在它的基础上写了题解qwq
分析
两数互质，且有无限个，想到不定方程ax+by=gcd(a,b)=1，并且是一定有解的
对于合法的数k,可以表示为 k=a×x1+b×y1(x1>=0,y1>=0)
找最大不合法的数，那么比它大的数（如k+1）一定是合法的，于是题目变成找最大的k使k-1不合法
由于本题中ax+by=1，对于不合法的数k-1,可以表示为
k-1=ax1+by1-(ax0+by0)=a(x1-x0)+b(y1-y0)
由ax0+by0=1，x0和y0必定不能同号
- 当 y0<0 ，有y1-y0>0 ，x0>0，只要x1-x0<0 则k-1不合法
- 当 x0<0 ，有x1-x0>0 ，y0>0，只要y1-y0<0 则k-1不合法
所以如果要k-1不合法，那么肯定所有x，y情况都不合法，即两式都要成立
所以对于1式，得x1<x0且x0>0，当x1<0自然无解，当x1>=0时，式1成立的条件是x1<所有非负x0，即x1<x'（x'是ax+by=1中x最小且非负的整数解）,那么最大的整数x1=x0-1,同理y1=y''-1 （y'' 是ax+by=1中y最小且非负的整数解）,使得两式都不合法, 而且k最大
ans=(x'-1)a+(y''-1)b-1
我们学到了什么
-
看范围 --1e9,互质等字眼,我们要用O(logn)的扩展欧几里得
-
转化问题 ——找最大的k使k-1不合法
-
式子标准化 ——将k-1用a(x1-x0)+b(y1-y0)的形式表示
-
探究不合法的条件 ——x1-x0<0,y1-y0'<0
-
贪心找最值 ——x1=x0-1,y1=y0-1
#include<cstdio>
using namespace std;
#define int long long
int a,b,x,y;
inline void exgcd(int a,int b,int &x,int &y) {
if (!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
signed main() {
scanf("%lld%lld",&a,&b);
exgcd(a,b,x,y),x=(x+b)%b,y=(y+a)%a;
printf("%lld",(x-1)*a+(y-1)*b-1);
}