Блог пользователя r.estrela

Автор r.estrela, история, 3 года назад, По-английски

Do i need to code a function everytime i wanna get the gcd of two long long variables or there is a easier solution?

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

gcd<int64_t>(x,y)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
__gcd <long long> (x, y)

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Is __gcd wrong with two long long variables? I always use it and have not seen any problems. A test case would be helpful. Thank you

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Why rely on an obscure, non-standard function (that might not work everywhere) when you can just implement the Euclidean algorithm yourself with only three lines of code (not counting braces)? If even that amount of typing bothers you, you can add it to your template.

long long GCD(long long x, long long y)
{
    if (y == 0) return x;
    return GCD(y, x%y);
}
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I know in some cases, it's necessary to have a fast gcd algorithm (I have heard of something like binary gcd before I believe), especially because there is modular arithmetic in the standard euclidian gcd algorithm. This probably isn't an issue for him but it's not impossible that he's searching for a fast version of gcd with long longs?