Как найти коэффициенты линейной комбинации из n чисел, которые дает их ГКД? - PullRequest
Новая
       31

Как найти коэффициенты линейной комбинации из n чисел, которые дает их ГКД?

0 голосов
/ 06 апреля 2019

У меня есть массив чисел, и я хочу, чтобы их соответствующие коэффициенты были такими, чтобы их линейная комбинация дала бы мне их наибольший общий делитель.

Я нашел, как это сделать для 2 чисел в этой ссылке .Но мне было интересно, как это сделать эффективно для массива чисел. 

ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0; 
        *y = 1; 
        return b; 
    } 

    ll x1, y1; // To store results of recursive call 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 

    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 

    return gcd; 
}

ll calc(ll gcd, int i)
{
    ll x,y;
    ll gcd_new = gcdExtended(gcd,conc[i],x,y);

    if (i == conc.size()-1)
    {
        return x;
    }
    ll temp = calc(gcd_new, i+1);
    x *= temp;
    y* = temp;

    return x;
}

Вот что я попробовал.ll обозначает long long int, а conc - глобальный вектор, содержащий числа, чей ГКД необходимо найти.

...