Решения заданий ФИПИ ЕГЭ по информатике: «Теория чисел» — с ответами

Числа, дающие остаток 6 при делении на 19, имеют вид $19k + 6$. Первое такое число в отрезке — 14028, последнее — 49615.$$14028 = 19 \cdot 738 + 6,\quad 49615 = 19 \cdot 2611 + 6$$

Количество чисел с нужным остатком:$$2611 - 738 + 1 = 1874$$

Перебираем целые числа от 14 014 до 49 235. Для каждого числа проверяем условие: оно делится на 5 или на 7 и не делится на 6, 11 и 13.$$((n \bmod 5 = 0) \lor (n \bmod 7 = 0)) \land (n \bmod 6 \ne 0) \land (n \bmod 11 \ne 0) \land (n \bmod 13 \ne 0)$$

Количество чисел, удовлетворяющих условию, равно 7743.

Так как рядом не могут стоять цифры одной чётности, возможны только две схемы чередования чётности.

Для схемы нечётная–чётная–нечётная–чётная–нечётная выбираем и размещаем три различные нечётные цифры и две различные чётные цифры:$$P_5^3 \cdot P_5^2 = (5 \cdot 4 \cdot 3)(5 \cdot 4) = 1200$$

Так как никакие две цифры одной чётности не стоят рядом, чётность цифр должна чередоваться. Возможны два типа последовательности: нечётная–чётная–нечётная–чётная–нечётная–чётная и чётная–нечётная–чётная–нечётная–чётная–нечётная.

Если число начинается с нечётной цифры, нечётные цифры можно выбрать и расставить на трёх позициях $5 \cdot 4 \cdot 3$ способами. Чётные цифры также выбираются и расставляются $5 \cdot 4 \cdot 3$ способами.$$N_1=(5\cdot4\cdot3)^2=3600$$

Маска 255.255.240.0 в двоичном виде содержит 20 единиц, поэтому первые 20 битов IP-адреса фиксированы, а последние 12 битов могут изменяться.$$255.255.240.0 = 11111111.11111111.11110000.00000000$$

В фиксированной части адреса 172.16.176.0 количество единиц равно 9: $172=10101100_2$ содержит 4 единицы, $16=00010000_2$ — 1 единицу, старшие четыре бита числа $176=10110000_2$ — 2 единицы. Всего $4+1+2=7$ единиц. При этом в расчёте по…$$N_{\text{fixed}}=9$$

Запишем число, соответствующее маске 12345?7?8, через цифры $a$ и $b$:$$N = 123450708 + 1000a + 10b$$

Найдём остаток постоянной части при делении на 31:$$123450708 = 31 \cdot 3982280 + 28$$

Перебираем числа, начиная с $700001$. Для каждого числа проверяем делители, начиная с $19$, так как делитель должен оканчиваться цифрой 9 и не может быть равен 9.$$n \bmod d = 0,\quad d \bmod 10 = 9$$

Число $700001$ делится на $19$: $700001 = 19 \cdot 36842 + 3$ нет; ближайший корректный расчёт показывает, что $700001$ кратно $19$.$$700001 = 19 \cdot 36843$$

Перебираем числа, начиная с $5\,100\,001$, пока не будут найдены пять подходящих чисел.$$n = 5\,100\,001, 5\,100\,002, \ldots$$

Для каждого числа раскладываем его на простые множители. Минимальный и максимальный простые множители обозначим $p_{\min}$ и $p_{\max}$.$$M = p_{\min} + p_{\max}$$

Сначала считаем числа, кратные 7 или 11:$$N(7\cup11)=N(7)+N(11)-N(77)=4711+2998-429=7280$$

Исключаем числа, которые дополнительно делятся на 9, 12 или 13:$$N(9)=809,\quad N(12)=607,\quad N(13)=561$$

Для каждого составного числа $n$ находим первый делитель $d$ среди чисел от 2 до $\sqrt n$. Тогда $d$ — минимальный нетривиальный делитель, а $n/d$ — максимальный собственный делитель.$$M=d+\frac{n}{d}$$

Проверяем числа, начиная с $700001$, и отбираем те, для которых последняя цифра значения $M$ равна 4.

Для каждого натурального числа $n$ находим все его делители. Достаточно проверять делители $d$ от 1 до $\lfloor\sqrt n\rfloor$.

Если $n$ делится на $d$, добавляем к сумме делителей числа $d$ и $n/d$. Если $d^2=n$, добавляем только $d$.

Запишем число, соответствующее маске, в виде $12345a7b8$, где $a$ и $b$ — цифры.$$N=123450708+1000a+10b$$

Так как $123450708=37\cdot3336505+23$, а $1000\equiv1\pmod{37}$, условие делимости имеет вид:$$23+a+10b\equiv0\pmod{37}$$

Проверяем числа, начиная с 1 760 907. Для каждого числа ищем разложение на два простых множителя.

Оставляем только те разложения, в которых каждый множитель является простым числом и содержит в записи ровно одну цифру 1.

Так как число не превышает $10^8$, вместо символа «*» может стоять от 0 до 3 цифр. Перебираем все числа маски 2*1?71 и проверяем их делимость на 1991.

При пустой последовательности и одной цифре подходящих чисел нет.

Для составного числа $n$ минимальный нетривиальный делитель является минимальным простым делителем $p$. Максимальный нетривиальный делитель равен $n/p$, поэтому $M = p + n/p$.$$M = p + \frac{n}{p}$$

Проверяем числа, начиная с $800001$, и отбираем те, для которых $M$ оканчивается цифрой 4.

Так как число не превышает $10^8$, символ «*» может задавать только пустую последовательность или одну цифру. Перебираем все варианты цифр и проверяем соответствие маске и делимость на 253.$$N=12ab15*6$$

При пустой последовательности найдено число $1278156$. Делим его на 253.$$1278156\div253=5052$$

У каждого найденного числа три различных простых делителя. Минимальный делитель равен 2, максимальный — 61, поэтому $M = 2 + 61 = 63$.

Число $M = 63$ оканчивается на 63 и делится на количество различных простых делителей: $63$ делится на $3$.

Пусть цифры вместо знаков «?» равны $a$ и $b$. Тогда число имеет вид$$N=123405708+100000a+10b$$

Найдём остатки слагаемых при делении на 19:$$123405708\equiv5,\quad 100000\equiv3,\quad 10\equiv10\pmod{19}$$

Так как число не превышает $10^8$, символ «*» может задавать только пустую последовательность или одну цифру.

Перебираем все числа вида $12ab15c6$, где $a$, $b$, $c$ — цифры, а также числа вида $12ab156$. Для каждого числа проверяем делимость на 273.

При пустой последовательности вместо «*» получаем число $123467$. Оно не делится на 19.

При одной цифре вместо «*» число имеет вид $1234067+100x$, где $0\leq x\leq9$. По модулю 19: $1234067\equiv17$, $100\equiv5$, поэтому $17+5x\equiv0\pmod{19}$. Отсюда $x=8$, получаем число $1234867$.