代码拉取完成,页面将自动刷新
同步操作将从 编程语言算法集/C-Sharp 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
using System.Numerics;
namespace Algorithms.ModularArithmetic
{
/// <summary>
/// Extended Euclidean algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.
/// </summary>
public static class ExtendedEuclideanAlgorithm
{
/// <summary>
/// Computes the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity,
/// which are integers x and y such that a*bezoutCoefficientOfA + b*bezoutCoefficientOfB = gcd(a, b).
/// </summary>
/// <param name="a">Input number.</param>
/// <param name="b">Second input number.</param>
/// <returns>A record of ExtendedEuclideanAlgorithmResult containing the bezout coefficients of a and b as well as the gcd(a,b).</returns>
public static ExtendedEuclideanAlgorithmResult<long> Compute(long a, long b)
{
long quotient;
long tmp;
var s = 0L;
var bezoutOfA = 1L;
var r = b;
var gcd = a;
var bezoutOfB = 0L;
while (r != 0)
{
quotient = gcd / r; // integer division
tmp = gcd;
gcd = r;
r = tmp - quotient * r;
tmp = bezoutOfA;
bezoutOfA = s;
s = tmp - quotient * s;
}
if (b != 0)
{
bezoutOfB = (gcd - bezoutOfA * a) / b; // integer division
}
return new ExtendedEuclideanAlgorithmResult<long>(bezoutOfA, bezoutOfB, gcd);
}
/// <summary>
/// Computes the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity,
/// which are integers x and y such that a*bezoutCoefficientOfA + b*bezoutCoefficientOfB = gcd(a, b).
/// </summary>
/// <param name="a">Input number.</param>
/// <param name="b">Second input number.</param>
/// <returns>A record of ExtendedEuclideanAlgorithmResult containing the bezout coefficients of a and b as well as the gcd(a,b).</returns>
public static ExtendedEuclideanAlgorithmResult<BigInteger> Compute(BigInteger a, BigInteger b)
{
BigInteger quotient;
BigInteger tmp;
var s = BigInteger.Zero;
var bezoutOfA = BigInteger.One;
var r = b;
var gcd = a;
var bezoutOfB = BigInteger.Zero;
while (r != 0)
{
quotient = gcd / r; // integer division
tmp = gcd;
gcd = r;
r = tmp - quotient * r;
tmp = bezoutOfA;
bezoutOfA = s;
s = tmp - quotient * s;
}
if (b != 0)
{
bezoutOfB = (gcd - bezoutOfA * a) / b; // integer division
}
return new ExtendedEuclideanAlgorithmResult<BigInteger>(bezoutOfA, bezoutOfB, gcd);
}
/// <summary>
/// The result type for the computation of the Extended Euclidean Algorithm.
/// </summary>
/// <typeparam name="T">The data type of the computation (i.e. long or BigInteger).</typeparam>
/// <param name="bezoutA">The bezout coefficient of the parameter a to the computation.</param>
/// <param name="bezoutB">The bezout coefficient of the parameter b to the computation.</param>
/// <param name="gcd">The greatest common divisor of the parameters a and b to the computation.</param>
public record ExtendedEuclideanAlgorithmResult<T>(T bezoutA, T bezoutB, T gcd);
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。