本文主要是介绍[算法学习] 贝祖定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
裴蜀定理: //设a,b是不全为0的整数,则存在整数x,y使得ax+by=gcd(a,b)
//扩展裴蜀定理: //a,b为不小于0的整数,n为整数,是否存在不小于0的x和y使得ax+by=n有解? //1、若n>ab-a-b,有解 //2、若n=0,有解(x=y=0) //3、若n<0,无解(a,b,x,y均不小于0,无法线性变换出负数) //4、若ax+by=n有解,则ax+by=ab-a-b-n无解
例题
1.最小正整数解 - 蓝桥云课 (lanqiao.cn)
//本题需要求解最小的ax+by=n,使得n>0 //设a和b的最大公约数为gcd(a,b),因为a,b,x,y均为整数,其线性组合同样是gcd(a,b)的倍数 //故ax+by=k*gcd(a,b) //令k=1,可得最小的ax+by=gcd(a,b) //故本题直接求解gcd(a,b)即可 //注意当ab异号时gcd(a,b)返回负数,需要取绝对值
这篇关于[算法学习] 贝祖定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
