gcd与扩展gcd
<h2>使用方法</h2>
<ol>
<li>
<p>使用命名空间</p>
<pre><code class="language-cpp">using namespace algorithm</code></pre>
</li>
<li>然后直接使用函数即可</li>
</ol>
<p>[========]</p>
<h2>函数说明</h2>
<p>函数<code>Type getGcd(Type a, Type b)</code> 计算a与b的最大公约数，返回Type类型</p>
<p>函数<code>Type getAnyCalc(Type a, Type b, Type c, Type1 &x, Type1 &y)</code> 计算ax+by=c的一组整数解</p>
<blockquote>
<p>注意：
当原式不可能存在整数解时，返回0
调用函数中之前，x与y不必赋初值，定义之后即可传入参数</p>
</blockquote>
<p>函数<code>Type getUpCalc(Type a, Type b, Type c, Type1 &x, Type1 &y)</code> 计算ax+by=c的最小非负整数解</p>
<blockquote>
<p>注意：
当原式不可能存在整数解时，返回0
调用函数中之前，x与y不必赋初值，定义之后即可传入参数
存在解但不存在最小非负整数解则计算靠近（0，0）的解
[========]</p>
</blockquote>
<h2>模板代码</h2>
<pre><code class="language-cpp">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;
}
};</code></pre>
<p>[========]</p>