Блог пользователя adviser

Alert : wrong gcd inbuild function in c++
Автор adviser, история, 2 года назад, По-английски

I was solving a question on gcd : (https://codeforces.com/contest/798/problem/C). here the inbuild function of gcd in c++ i.e __gcd(a,b) gives the wrong answer. the gcd of -2 and 4 should be 2. but inbuild function in sublime gives answer -2. can anyone explain why? later when i searced i founded that __gcd(a,b) == __gcd(|a|,|b|) but there is no where written that you only have to pass non negative number in GCD funtion in c++. thank you in advance.

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

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

As i am newbie please don't just do downvote and go. if you cannot help atleast don't downvote. I am learning things. and it will take some time for me to learn and reach red

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The implementation might differ depending on compiler, but this is the implementation of __gcd in MinGW 10.2.0 for example:

Under spoiler cause image is big

As you can see, the implementation doesn't care about positives or negatives. If you trace the code for your specific input, you'll see why it's -2.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

If you want to get the abs of the answer, use std::gcd in C++17 instead.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Try to use gcd instead of __gcd:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = -2, b = 4;
    cout << __gcd(a,b) << endl;
    cout << gcd(a,b) << endl;
}

Output:

-2
2
→ Ответить