题解 P3951 小凯的疑惑

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必定不能同号

当 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);

}

巴特西

题解 P3951 小凯的疑惑

分析

我们学到了什么

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

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

最新文章

热门文章