Binarny GCD nie wypali bo przecież w standardzie nie ma funkcji które wczytują liczby rzędu 10^100 i konwertują na postać binarną. Jeśli użyjesz dodatkowej biblioteki, np GMP to równie dobrze mógłbyś użyć funkcji modulo z GMP.
Wykorzystaj mój sposób. Nie wykorzystuje on modulo (reszty z dzielenia) wprost.
Kod poglądowy:
#include <cstdio>
int potega(int podstawa, int wykladnik) {
return wykladnik ? potega(podstawa, wykladnik - 1) * podstawa : 1;
}
//#define MOZNA_UZYWAC_MODULO
#define UZYJ_HYBRYDY
int gcd(int a, int b) {
#ifdef MOZNA_UZYWAC_MODULO
a %= b;
#else
#ifdef UZYJ_HYBRYDY
int wykladnik = 0;
while (a >= b * potega(10, wykladnik + 1)) {
wykladnik++;
}
if (a >= b) {
a -= b * potega(10, wykladnik);
}
#endif
while (a >= b) {
a -= b;
}
#endif
return a ? gcd(b, a) : b;
}
int main(int argc, char** argv) {
printf("%d\n", gcd(95675769, 5675768));
return 0;
}
Oczywiście zamiast intów będziesz miał stringi i zamiast mnożenia przez potęgi 10 będziesz miał doklejanie znaku '0' na koniec stringa.
PS:
Cały kod w #if to albo dzielenie modulo, albo emulacja dzielenia modulo - tak, powtarzane odejmowanie to emulowanie dzielenia modulo.
Edit:
Mam kod, trochę działa ale na testach się wywłaszcza (tylko 14 pkt zdobywa):
#include <iostream>
#include <string>
std::string odejmij(const std::string a, const std::string b) {
std::string w;
std::string::const_reverse_iterator ita = a.rbegin();
std::string::const_reverse_iterator itb = b.rbegin();
bool pozyczenie = false;
char c;
while (itb != b.rend()) {
if (pozyczenie) {
c = (*ita >= *itb + 1 ? *ita - *itb - 1 : *ita - *itb + 9) + '0';
pozyczenie = *ita < *itb + 1;
} else {
c = (*ita >= *itb ? *ita - *itb : *ita - *itb + 10) + '0';
pozyczenie = *ita < *itb;
}
w = c + w;
ita++;
itb++;
}
if (ita != a.rend()) {
if (pozyczenie) {
c = *ita - 1;
w = c + w;
ita++;
}
while (ita != a.rend()) {
c = *ita;
w = c + w;
ita++;
}
}
while ((w.size() > 1) && (w[0] == '0')) {
w = w.substr(1, w.size() - 1);
}
return w;
}
std::string gcd(std::string a, std::string b) {
std::string c(b);
while ((a.size() > c.size() + 1) || ((a.size() == c.size() + 1) && (a >= c + '0'))) {
c += '0';
}
if ((a.size() > c.size()) || ((a.size() == c.size()) && (a >= c))) {
a = odejmij(a, c);
}
while ((a.size() > b.size()) || ((a.size() == b.size()) && (a >= b))) {
a = odejmij(a, b);
}
return a != "0" ? gcd(b, a) : b;
}
int main(int argc, char** argv) {
//std::cout << odejmij("996", "995") << std::endl;
//std::cout << gcd("95675769", "5675768") << std::endl;
std::string a;
std::string b;
std::cin >> a >> b;
while ((a.size() > 1) && (a[0] == '0')) {
a = a.substr(1, a.size() - 1);
}
while ((b.size() > 1) && (b[0] == '0')) {
b = b.substr(1, b.size() - 1);
}
std::cout << gcd(a, b) << std::endl;
return 0;
}