V🇺
а, понял
Size: a a a
2020 October 13
A
короче, для любых двух чисел на какой-то итерации мы получим их gcd
@N
k * gcd всех?
+
ЕВ
Хм..
Это нужно осмыслить, спасибо🤔🤔
Это нужно осмыслить, спасибо🤔🤔
V🇺
там же largest, а не smallest
A
для любого числа k и k*N мы можем получить все значения 2k, 3k .. (N-1)k
@N
там же largest, а не smallest
А, точно
A
короче мы так или иначе заметем все от 0 до max этого множества сеткой в gcd
@N
там же largest, а не smallest
Тогда наоборот, с max - (k-1)*gcd
V🇺
да, так похоже на правду
ЕВ
для любого числа k и k*N мы можем получить все значения 2k, 3k .. (N-1)k
Да, с этим согласен. Но разве из этого следует, что в конце будет множество вида
gcd, 2*gcd, 3*gcd, ..., k* gcd?
gcd, 2*gcd, 3*gcd, ..., k* gcd?
A
по-моему да
A
то есть как. Пусть для простоты gcd равен 1. У нас есть число N и мы хотим доказать, что в множестве будут все от 1 до N. Ну это просто - сначала добавим в него разность между N и 1, то есть N-1. Потом разность между ним и 1 и так далее
@N
Да, с этим согласен. Но разве из этого следует, что в конце будет множество вида
gcd, 2*gcd, 3*gcd, ..., k* gcd?
gcd, 2*gcd, 3*gcd, ..., k* gcd?
1. gcd когда-то получим
2. max, gcd: max - gcd
3. max - gcd, gcd: max - 2gcd
...
2. max, gcd: max - gcd
3. max - gcd, gcd: max - 2gcd
...
ЕВ
Я понял, спасибо всем.✊
CD
то есть как. Пусть для простоты gcd равен 1. У нас есть число N и мы хотим доказать, что в множестве будут все от 1 до N. Ну это просто - сначала добавим в него разность между N и 1, то есть N-1. Потом разность между ним и 1 и так далее
что тут доказывать-то, Евклид над любой парой будет выполнен
A
ну в смысле пусть у нас числа 30 и 9. Да, эвклидом мы получим число 3. Но как доказать, что число 24 тоже будет в ответе.
A
30 и 9. Первой итерацией мы добавим туда 21. Второй итерацией мы добавим 12. Третьей итерацией добавим 3 и 18.
ЕВ
ну в смысле пусть у нас числа 30 и 9. Да, эвклидом мы получим число 3. Но как доказать, что число 24 тоже будет в ответе.
Да, именно👌👌
A
А вот дальше мы просто со временем получим все числа кратные 3