gcd与扩展gcd

使用方法

1. 使用命名空间

   using namespace algorithm

2. 然后直接使用函数即可

[========]

函数说明

函数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;
    }
};

[========]