gcd与扩展gcd
使用方法
-
使用命名空间
using namespace algorithm
- 然后直接使用函数即可
[========]
函数说明
函数Type getGcd(Type a, Type b)
计算a与b的最大公约数,返回Type类型
函数Type getAnyCalc(Type a, Type b, Type c, Type1 &x, Type1 &y)
计算ax+by=c的一组整数解
> 注意:
> 当原式不可能存在整数解时,返回0
> 调用函数中之前,x与y不必赋初值,定义之后即可传入参数
函数Type getUpCalc(Type a, Type b, Type c, Type1 &x, Type1 &y)
计算ax+by=c的最小非负整数解
> 注意:
> 当原式不可能存在整数解时,返回0
> 调用函数中之前,x与y不必赋初值,定义之后即可传入参数
> 存在解但不存在最小非负整数解则计算靠近(0,0)的解
[========]
模板代码
namespace algorithm{
template <class Type>
Type getGcd(Type a, Type b){
if(b == 0) return a;
else return getGcd(b, a%b);
}
template <class Type, class Type1>
Type getExgcd(Type a, Type b, Type1 &x, Type1 &y){
if(b == 0){
x = (Type1)1, y = (Type1)0;
return a;
}
Type gcd = getExgcd(b, a%b, x, y);
Type rx = x;
x = y;
y = rx - (Type1)a / b * y;
return gcd;
}
template <class Type, class Type1>
Type getAnyCalc(Type a, Type b, Type c, Type1 &x, Type1 &y){
Type gcd = getExgcd(a, b, x, y);
if(c % gcd) return 0;
Type transit = c / gcd;
x *= (Type1)transit;
y *= (Type1)transit;
return gcd;
}
template <class Type, class Type1>
Type getUpCalc(Type a, Type b, Type c, Type1 &x, Type1 &y){
Type gcd = getExgcd(a, b, x, y);
if(c % gcd) return 0;
Type transit = c / gcd;
x *= (Type1)transit; y *= (Type1)transit;
Type _a = a,_b = b;
a /= gcd; b /= gcd;
x = x % b < 0? x % b + (b < 0? -b: b): (x % b);
y = y % a < 0? y % a + (a < 0? -a: a): (y % a);
if(c < 0) y = (c - _a * x) / _b;
else x = (Type1)(c - _b * y) / _a;
return gcd;
}
};
[========]