Największy wspólny dzielnik- błąd na uczelnianej sprawdzarce

0

Cześć,
mam za zadania obliczyć NWD(x, a*x+b) dla podanych w wejściu liczb naturalnych a,b,x (1 ≤ x, a, b ≤ 10^15). Np. dla liczb 100 17 42 wynik to 2.

Mój kod daje poprawne dane, ale na uczelnianej sprawdzarce na 6 linii daje akceptem w pięciu liniach - w linii 2 jest wrong answer. Nie wiem za bardzo, gdzie jest ten błąd, więc może Wam się coś rzuci.

#include <iostream>
using namespace std;

unsigned long long nwd(unsigned long long x, unsigned long long b) {
     unsigned long long pom;

    while(b!=0)
    {
        pom = b;
        b = x%b;
        x = pom;
    }

    return x;
}

int main()
{
    unsigned long long x,a,b;
    cerr<<"Wprowadz liczbe x a b: ";
    cin>>x>>a>>b;
    cerr<<"Wynik: ";
    cout<<nwd(x,a*x+b)<<endl;
    return 0;
}
1

Pewnie Masz overflow w a*x+b. Zauważ, że gcd(a, b) = gcd(a, a*v + b)

0

A masz pomysł jak mogę się go pozbyć? Czy szukać jakieś prawidłowości dla dużych liczb z resztami?

1

Poprawione formatowanie bo czytać się nie da:

#include <iostream>
using namespace std;

unsigned long long nwd(unsigned long long x, unsigned long long b)
{
    unsigned long long pom;

    while (b != 0) {
        pom = b;
        b = x % b;
        x = pom;
    }

    return x;
}

int main()
{
    unsigned long long x, a, b;
    cerr << "Wprowadz liczbe x a b: ";
    cin >> x >> a >> b;
    cerr << "Wynik: ";
    cout << nwd(x, a * x + b) << endl;
    return 0;
}
3

unsigned long long pom;
unsigned long long nwd(unsigned long long x, unsigned long long b)

brzmi jak refren jakiejś piosenki

Unsiigned! Long long pom!
Unsigned! long long N.W.D!
Unsigned! long, long ex.
Unsigned! long, long be!

0

@lion137 - rzeczywiście napisałeś to mega prosto :) Ja nie blondynka, a jednak... Uznajmy to za późną porę i chwilowe zaćmienie;) Wielkie dzięki, bo oczywiście wszystko przeszło :)
@LukeJL - bez śmiechów mi tu ;) Choć zacne podsumowanie tematu - niestety;)
@TobiP - uczę się od 2 msc, więc 40lat doświadczenia to nie mam, ale google, różne kursiki online i dostępne kody przychodzą mi z pomocą w wielu kwestiach. Niestety podyplomówka mnie zawiodła, bo liczyłam na naukę od podstaw i na realizację zadań, które mogą się przydać w pracy, a tymczasem więcej nauczyłabym się sama z pomocą neta. Zrozumiałam, że wyszłam poza obszar pamięci ;)

Życzę wszystkim udanego piątku :)

0

Tak nie do końca. Nie wyszłaś poza obszar w pamięci. Nie zmieściłaś się w pamięci, wynik został zaledwie przycięty.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0