P3951 小凯的疑惑

数论极菜的小萌新我刚看这题时看不懂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必定不能同号

  1. 当 y00 ，x0>0，只要x1-x0<0 则k-1不合法
  2. 当 x00 ，y0>0，只要y1-y0<0 则k-1不合法

所以如果要k-1不合法，那么肯定所有x，y情况都不合法，即两式都要成立

所以对于1式，得x1 0，当x1=0时，式1成立的条件是x1

ans=(x'-1)a+(y''-1)b-1

我们学到了什么

  1. 看范围 --1e9,互质等字眼,我们要用O(logn)的扩展欧几里得

  2. 转化问题 ——找最大的k使k-1不合法

  3. 式子标准化 ——将k-1用a(x1-x0)+b(y1-y0)的形式表示

  4. 探究不合法的条件 ——x1-x0<0,y1-y0'<0

  5. 贪心找最值 ——x1=x0-1,y1=y0-1

#include
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);
}

关于进一步的ab-a-b做法推荐这个博客

还有一种比较简单的理解方法:这个博客