二元一次不定方程的整数解(扩展欧几里得算法)
(不得不说这是一堂数学*信竞课)
整数解解法
c(mod b)或ax+by=c有整数解当且仅当(a,b)|c
一般意义下的解法:
欧拉函数
扩展欧几里得算法
代码实现
exgcd返回值为(a,b)
int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return a;}int r=exgcd(b,a%b,y,x);y-=x*(a/b);return r;}
(x,y为特解)
通解:
符合要求的特解的寻找
例1. x最小的非负整数值
解:找到x最接近于0的点后往前后枚举
例2. |x+y|最小的解
解:将ax+by=c化成y=kx+b,那么|x+y|=|(k+1)x+b|,写出分段函数(两段)
例3. m|x|+n|y|最小/大的解
解:m|x|+n|y|=m|x|+n|kx+b|,写出分段函数(最多三段)
例4. x,y均为正数,mx+ny最小/大
解:mx+ny=(kn+m)x+bn,根据kn+m的正负性讨论即可。