Нахождение неизвестных множителя, делимого или делителя

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.

Получите невероятные возможности

1. Откройте доступ ко всем видеоурокам комплекта. 2. Раздавайте видеоуроки в личные кабинеты ученикам. 3. Смотрите статистику просмотра видеоуроков учениками.

Нет, спасибо

Получить доступ

Нахождение неизвестного множителя

Посмотрим на два уравнения: $x·2=20$ и $3·x=12$. В обоих нам известно значение произведения и один из множителей, необходимо найти второй. Для этого нам надо воспользоваться другим правилом.

Для нахождения неизвестного множителя нужно выполнить деление произведения на известный множитель.

Данное правило базируется на смысле, который является обратным смыслу умножения. Между умножением и делением есть следующая связь: $a·b=c$ при $a$ и$b$, не равных $$, $c: a=b$, $c: b=c$ и наоборот.

Вычислим неизвестный множитель в первом уравнении, разделив известное частное 20 на известный множитель 2. Проводим деление натуральных чисел и получаем 10. Запишем последовательность равенств: x·2=20x=20:2x=10. Подставляем десятку в исходное равенство и получаем, что 2·10=20. Значение неизвестного множителя было выполнено правильно.

Читайте также: Как найти группу в WoW Classic / World of Warcraft

Уточним, что в случае, если один из множителей нулевой, данное правило применять нельзя. Так, уравнение $x·=11$ с его помощью решить мы не можем. Эта запись не имеет смысла, поскольку для решения надо разделить $11$ на $$, а деление на нуль не определено. Подробнее о подобных случаях мы рассказали в статье, посвященной линейным уравнениям.

Когда мы применяем это правило, мы, по сути, делим обе части уравнения на другой множитель, отличный от $$. Существует отдельное правило, согласно которому можно проводить такое деление, и оно не повлияет на корни уравнения, и то, о чем мы писали в этом пункте, с ним полностью согласовано.

Видео

Расширенный алгоритм Евклида*

Очень важным для математики свойством наибольшего общего делителя является следующий факт:

Для любых целых \(a, b\) найдутся такие целые \(x, y\), что \(ax + by = d\), где \(d = \gcd(a, b)\).

Из этого следует, что существует решение в целых числах, например, у таких уравнений: * \(8x + 6y = 2\) * \(4x — 5y = 1\) * \(116x + 44y = 4\) * \(3x + 11y = -1\)

Мы сейчас не только докажем, что решения у таких уравнений существуют, но и приведем быстрый алгоритм нахождения этих решений. Здесь нам вновь пригодится алгоритм Евклида.

Рассмотрим один шаг алгоритма Евклида, преобразующий пару \((a, b)\) в пару \((b, a \operatorname{\%} b)\). Обозначим \(r = a \operatorname{\%} b\), то есть запишем деление с остатком в виде \(a = bq + r\).

Предположим, что у нас есть решение данного уравнения для чисел \(b\) и \(r\) (их наибольший общий делитель, как известно, тоже равен \(d\)): \[bx_0 + ry_0 = d\]

Теперь сделаем в этом выражении замену \(r = a — bq\):

\[bx_0 + ry_0 = bx_0 + (a — bq)y_0 = ay_0 + b(x_0 — qy_0)\]

Tаким образом, можно взять \(x = y_0\), а \(y = (x_0 — qy_0) = (x_0 — (a \operatorname{/} b)y_0)\) (здесь \(/\) обозначает целочисленное деление).

В конце алгоритма Евклида мы всегда получаем пару \((d, 0)\). Для нее решение требуемого уравнения легко подбирается — \(d * 1 + 0 * 0 = d\). Теперь, используя вышесказанное, мы можем идти обратно, при вычислении заменяя пару \((x, y)\) (решение для чисел \(b\) и \(a \operatorname{\%} b\)) на пару \((y, x — (a / b)y)\) (решение для чисел \(a\) и \(b\)).

Это удобно реализовывать рекурсивно:

Но также полезно и посмотреть, как будет работать расширенный алгоритм Евклида и на каком-нибудь конкретном примере. Пусть мы, например, хотим найти целочисленное решение такого уравнения: \[116x + 44y = 4\] \[(2\times44+28)x + 44y = 4\] \[44(2x+y) + 28x = 4\] \[44x_0 + 28y_0 = 4\] Следовательно, \[x = y_0, y = x_0 — 2y_0\] Будем повторять такой шаг несколько раз, получим такие уравнения: \[116x + 44y = 4\] \[44x_0 + 28y_0 = 4, x = y_0, y = x_0 — 2y_0\] \[28x_1 + 16y_1 = 4, x_0 = y_1, y_0 = x_1 — y_1\] \[16x_2 + 12y_2 = 4, x_1 = y_2, y_1 = x_2 — y_2\] \[12x_3 + 4y_3 = 4, x_2 = y_3, y_2 = x_3 — y_3\] \[4x_4 + 0y_4 = 4, x_3 = y_4, y_3 = x_4 — 3 y_4\] А теперь свернем обратно: \[x_4 = 1, y_4 = 0\] \[x_3 = 0, y_3 =1\] \[x_2 = 1, y_2 =-1\] \[x_1 = -1, y_1 =2\] \[x_0 = 2, y_0 =-3\] \[x = -3, y =8\]

Действительно, \(116\times(-3) + 44\times8 = 4\)

Решето Эратосфена

Часто нужно не проверять на простоту одно число, а найти все простые числа до \(N\). В этом случае наивный алгоритм будет работать за \(O(N\sqrt N)\), так как нужно проверить на простоту каждое число от 1 до \(N\).

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до \(N\) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Красивая визуализация

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число \(i\) имеет смысл перебирать только до корня из \(N\), потому что при зачеркивании составных чисел, делящихся на простое \(i > \sqrt N\), мы ничего не зачеркнем. Почему? Пусть существует составное \(M \leq N\), которое делится на %i%, и мы его не зачеркнули. Но тогда \(i > \sqrt N \geq \sqrt M\), а значит по ранее нами доказанному утверждению \(M\) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине \(j\) имеет смысл перебирать только начиная с \(i^2\). Зачем вычеркивать \(2i\), \(3i\), \(4i\), …, \((i-1)i\), если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на \(2\), \(3\), \(4\), …, \((i-1)\).

Асимптотика

Такой код будет работать за \(O(N \log \log N)\) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Научимся оценивать асимптотику величины \(1 + \frac{1}{2} + \ldots + \frac{1}{N}\), которая нередко встречается в задачах, где фигурирует делимость.

Возьмем \(N\) равное \(2^i — 1\) и запишем нашу сумму следующим образом: \[\left(\frac{1}{1}\right) + \left(\frac{1}{2} + \frac{1}{3}\right) + \left(\frac{1}{4} + \ldots + \frac{1}{7}\right) + \ldots + \left(\frac{1}{2^{i — 1}} + \ldots + \frac{1}{2^i — 1}\right)\]

Каждое из этих слагаемых имеет вид \[\frac{1}{2^j} + \ldots + \frac{1}{2^{j + 1} — 1} \le \frac{1}{2^j} + \ldots + \frac{1}{2^j} = 2^j \frac{1}{2^j} = 1\]

Таким образом, наша сумма не превосходит \(1 + 1 + \ldots + 1 = i \le 2\log_2(2^i — 1)\). Тем самым, взяв любое \(N\) и дополнив до степени двойки, мы получили асимптотику \(O(\log N)\).

Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением \(\frac{1}{2}\).

Попытка объяснения асимптотики** (для старших классов)

Мы знаем, что гармонический ряд \(1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{N}\) это примерно \(\log N\), а значит \[N + \frac{N}{2} + \frac{N}{3} + \ldots + \frac{N}{N} \sim N \log N\]

А что такое асимптотика решета Эратосфена? Мы как раз ровно \(\frac{N}{p}\) раз зачеркиваем числа делящиеся на простое число \(p\). Если бы все числа были простыми, то мы бы как раз получили \(N \log N\) из формули выше. Но у нас будут не все слагаемые оттуда, только с простым \(p\), поэтому посмотрим чуть более точно.

Известно, что простых чисел до \(N\) примерно \(\frac{N}{\log N}\), а значит допустим, что k-ое простое число примерно равно \(k ln k\). Тогда

\[\sum_{\substack{2 \leq p \leq N \\ \text{p is prime}}} \frac{N}{p} \sim \frac{1}{2} + \sum_{k = 2}^{\frac{N}{\ln N}} \frac{N}{k \ln k} \sim \int_{2}^{\frac{N}{\ln N}} \frac{N}{k \ln k} dk =N(\ln\ln\frac{N}{\ln N} — \ln\ln 2) \sim N(\ln\ln N — \ln\ln\ln N) \sim N \ln\ln N\]

Но вообще-то решето можно сделать и линейным.

Последовательное применение правил

Зачастую на практике встречаются более сложные задачи, в которых правила нахождения слагаемых, уменьшаемых, вычитаемых, множителей, делимых и частных нужно применять последовательно. Приведем пример.

У нас есть уравнение вида 3·x+1=7. Вычисляем неизвестное слагаемое 3·x, отняв от 7 единицу. Получим в итоге 3·x=7−1, потом 3·x=6. Это уравнение решить очень просто: делим 6 на 3 и получаем корень исходного уравнения. Вот краткая запись решения еще одного уравнения (2·x−7):3−5=2: (2·x−7):3−5=2,(2·x−7):3=2+5,(2·x−7):3=7,2·x−7=7·3,2·x−7=21,2·x=21+7,2·x=28,x=28:2,x=14.

Всё ещё сложно? Наши эксперты помогут разобраться Все услуги

Теги