nwd z informacją o sumie

[Smilek22]

Suma dwóch liczb naturalnych dodatnich jest równa 777. Jaka największą wartość może
przyjąć ich największy wspólny dzielnik?

Mnie wyszło, że 37. Zrobiłam to jednak nieco chaotycznie, dlatego proszę o pomoc w rozwiązaniu.

[mortan517]

Źle. Zobacz chociażby tu:
\(\displaystyle{ x=333 \ \ y=444 \\ NWD(x,y)=111}\)

[gryxon]

\(\displaystyle{ NWD(259,518)=259}\)

To jest największy.

Kod: Zaznacz cały

#include <iostream>
using namespace std;
int max(int a, int b){
	if(a>b)return a;
	else return b;
}
int nwd(int a, int b){
	if(b==0)return a;
	else return nwd(b,a%b);
}
int main() {
	int maxi = 0;
	for(int i = 1; i<=776;++i){
		maxi=max(nwd(i,777-i),maxi);
	}
	cout << maxi;
	return 0;
}

Koniec dowodu? ;p

Jak to ładnie zrobić?

[Hydra147]

Niech \(\displaystyle{ NWD(x,y)=d}\) oraz \(\displaystyle{ x+y=777}\). Mamy zatem \(\displaystyle{ d|x}\) i \(\displaystyle{ d|y}\) czyli \(\displaystyle{ d|x+y=777}\). Największym dzielnikiem liczby 777 mniejszym od niej samej jest oczywiście 259 i jest on osiągalny np. dla \(\displaystyle{ x=518}\) oraz \(\displaystyle{ y=259}\).

[Smilek22]

Faktycznie, pominęłam 259. Dziękuję bardzo za ładne wyjaśnienia. Zwłaszcza Hydra147.