Как вычислить число итераций алгоритма Евклида через вычитание?

Question

[demon trigger]

Нужно вычислить чисто итераций, производимых алгоритмом евклида через вычитание. Число итераций нужно именно от способа с вычитанием, но проблема такого способа в том, что с большими числами он работает очень долго, а лимит все 1 секунда.

Answer 1

[Wataru]

Алгоритм через деление с остатоком - это всего-лишь оптимизация алгоритма через вычитание. Просто куча вычитаний делается скопом. Так же можно их все и подсчитать. Просто прибавляйте каждый раз не 1, а сколько там раз меньшее число в большее помещается. Типа answer += b/a

Comments

[demon trigger]

#include <iostream>
using namespace std;

int main() {
    long long int A, B, X = 0;
    cin >> A >> B;
    while(A != 0 && B != 0) {
        if(A > B) {
            A = A % B;
            X += B / A;
        } else {
            B = B % A;
            X += A / B;
        }
    }
    cout << X;
    return 0;
}

написал вот такой код, но есть одна проблема, если A или B становится 0, то получается ошибка. Не могу придумать, как это обойти, если просто ставить ифы, то не работают случаи, когда остаток от деления равен 0.

[Wataru]

demon trigger, Вы к ответу прибавляйте до изменения. И еще у вас порядок перепутан. Там где вы по модулю B берете (делите с остатоком) - там надо и нацело на B делить. Остаток же он от этого деления и остается. Вот было у вас большое A. Вы его на B поделили. Остаток остался. Частное - количество вычитаний.