Dwuwymiarowe żabki - szkopuł

Question

Witam, 

Ostatnio chciałem sobie porobić zadania bardziej "do pomyślenia", zrobiłem kilka i utknąłem na zadaniu "Dwuwymiarowe żabki". https://szkopul.edu.pl/problemset/problem/jhX8ocY37sY3QxmzJLwFrWC1/site/?key=statement

Oto kod:

#include <iostream>

struct Ab {
	Ab()
	{

	}

	Ab(unsigned long int a, unsigned long int b) : a(a), b(b)
	{

	}

public:
	unsigned long int a;
	unsigned long int b;
};

int main()
{
	int n;
	std::cin >> n;

	Ab* dimensions = new Ab[n];
	for (int i = 0; i < n; i++) {
		unsigned long int a, b;
		std::cin >> a >> b;

		dimensions[i] = Ab(a, b);
	}

	for (int i = 0; i < n; i++) {
		Ab dim = dimensions[i];
		if (dim.a == dim.b) {
			std::cout << 1 << std::endl;
			continue;
		}

		int count = 1;
		while (dim.a != dim.b) {
			if (dim.a > dim.b) {
				std::swap(dim.a, dim.b);
			}

			dim.b -= dim.a;
			count++;
		}

		std::cout << count << std::endl;
	}

	return 0;
}

Zalicza mi wszystkie testy oprócz dwóch ostatnich:

Pojęcia nie mam czemu tak się dzieje - co powoduje problem w tym kodzie?

Answer 1

1) integer overflow. Wynik może być rzędu 1e18 co nie zmieści się w int.

2) algorytm jest za wolny. Może wykonać nawet 1e18 kroków

Comments

Bardziej chodziło mi o wyjaśnienie zasady działania, z czego to wynika. Widzę, że dzielisz przez siebie dwa boki prostokąta i mnożysz przez jeden z boków. I dodać resztę z dzielenia tych boków. Ale z czego taka operacja wynika? Chciałbym poznać ciąg rozumowania (od początku do końca) który do takich wniosków prowadzi. Bo mój rozumek jest zbyt tępy żeby samemu do tego dojść.

---

Mogę powiedzieć na czym polega rozwiązanie, ale czy rozumiesz dlaczego powyższy wzór wgl działa?

---

Poza tym, że zadziała, i że zrobi to obojętnie czy a>b czy b>a, to nie rozumiem dlaczego tak jest. Ale myślę, że gdybym prześledził rozwiązanie (na czym polega) to mnie oświeci.

---

floor(a / b) mówi ile razy b mieści się w a.  Czyli w a mamy floor(a / b) pełnych b, ale do pełnego a brakuje a - floor(a / b) * b, co zdefiniowane jest jako a % b. Zatem:

a - floor(a / b) * b = a % b

a = floor(a / b) * b + a % b

Teraz jeden krok w algorytmie Euklidesa (tym wolniejszym) polegał na odjęciu mniejszej liczby od większej. Bez strat ogólności załóżmy a > b. Ale co jeśli np.  a = 11, b = 2? Będziemy robić:

a = 11 - 2 = 9, b = 2

a = 9 - 2 = 7, b = 2

...

Widać, że tych odejmowań jest dużo. A co jeśli skompresować te odejmowania do jednego kroku? Możemy skorzystać z tego, ze umiemy też dzielić i mnożyć. Skoro w 11 mieści się floor(11 / 2) = 5 dwójek, to odejmijmy 5 dwójek w jednym kroku, zamiast odejmować jedną dwójkę w 5 krokach. Co dostaniemy jak odejmiemy wszytkie dwójki? 11 % 2, czyli 1. Teraz możemy zmienić a z b, czyli a = 2, b = 1 i powtarzamy.

Widać, że wykonalismy tak naprawdę operację a' = b,  b' = a % b, Co więcej wykonalismy ją w jednym kroku, co znacznie przyspiesza algorytm.

Do rozwiązania zadania wystarczy zauważyć, że trzeba sumować floor(a / b)

---

Przespałem się i teraz to aż wstyd za tą tępote xD Ale przynajmniej teraz rozumiem, wielkie dzięki!