1386. Точные квадраты
Точные квадраты
Элементы теории чисел, диофантовы уравнения
Олимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание ( 1A) |
| 24/06/2010 | Лето 2010 — 1 (A) |
| 18/09/2010 | Занятие 2 (E) |
| 27/06/2016 | Лето 2016 — 1 (A) |
| 26/09/2019 | Соревнование 1 курса ВШЭКН, ВШЭУ (E) |
| 28/06/2023 | Лето 2023-2 простые (B) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Целое число `N` называется точным квадратом, если оно является квадратом какого-либо целого числа, то есть существует такое целое `S` , что `N\ =\ S^2` .
Даны целые числа `F` и `L` . Требуется найти количество точных квадратов от `F` до `L` включительно.
Например, от 5 до 25 включительно три точных квадрата – `9\ =\ 3^2` , `16\ =\ 4^2` и `25\ =\ 5^2` .
В первой строке входного файла содержатся два целых числа `F` и `L` ( `0 ≤ F ≤ L ≤ 10^9` ).
Выведите в выходной файл одно искомое число.
Точные квадраты и кубы
Из основной теоремы арифметики следует, что точный квадрат всегда имеет нечетное число делителей: если число $a=p_^<\alpha_>\times p_^<\alpha_>\times\ldots\times p_^<\alpha_>$ есть точный квадрат, то показатели степеней $\alpha_,\alpha_,\ldots,\alpha_$, четны, а число делителей числа a, равное $(\alpha_+1)(\alpha_+1)\ldots(\alpha_+1)$ нечетно.
Точно так же у точного куба число делителей имеет вид 3n+1, у четвертой степени — число вида 4n+11 и т.д.
При работе со степенями целых и натуральных чисел всегда следует иметь в виду, что степень с большим показателем также является и степенью с маленьким показателем: например, а 100 — это одновременно и квадрат пятидесятой степени, и четвертая степень двадцать пятой степени, и пятая степень двадцатой степени, и т.п. Ясно, что показатель степени таким образом можно уменьшить для любого составного числа n, а для простого n это ничего не даст.
При решении задач полезным может оказаться следующее свойство точных квадратов:
Квадрат числа при делении на любое число дает тот же остаток, что и квадрат его остатка.
Действительно, если r — остаток от деления k на b, то k 2 и r 2 дают при делении на b один и тот же остаток: $k^2-r^2=(k-r)(k+r)$, а k-r делится на b.
Например, число k при делении на 6 может давать остатки 0, 1, 2, 3, 4, 5, их квадраты — 0, 1, 4, 9, 16, 25, а остатки от деления квадратов на 6 — это 0, 1, 4, 3, 4, 1. Таким образом, квадрат числа при делении на 6 не может давать остатков 2 и 5.
Теми же рассуждениями легко получить, что возможные остатки при делении точного квадрата на 3 и на 4 — это 0 или 1.
Пример 1: Является ли число $123^2+345^2+567^2$ точным квадратом?
Ответ: Все три числа в заданной сумме нечетны, следовательно, их квадраты имеют вид 4п+1, так что их сумма имеет вид 4т+3 и поэтому не является точным квадратом.
Пример 2: Является ли число $[50\pi]^2+[100\pi]^2$ точным квадратом?
Ответ: Поскольку числа $[50\pi]$, $[100\pi]$ — это на самом деле 157 и 314, то оба они не делятся на 3, и поэтому их квадраты имеют вид Зn+1, а сама заданная сумма имеет вид 3m+2 и, следовательно, не является точным квадратом
Пример 3: Доказать, что если два числа оба не делятся на 3, то их сумма не является точным квадратом.
Ответ: Так как квадрат любого натурального числа, не делящегося на 3, при делении на 3 дает остаток 1, то сумма любых двух таких чисел при делении на 3 дает остаток 2, а такое число не может быть точным квадратом.
Материалы по теме:
- «Целые остатки»
- Основная теорема арифметики
- Малая теорема Ферма
- Признаки делимости на 4, 8, 11 и 25
Что такое точный квадрат
Будем называть натуральное число почти квадратом, если это либо точный квадрат, либо точный квадрат, умноженный на простое число.
Могут ли 8 почти квадратов идти подряд?
Решение
Пусть такие числа нашлись.
Первый способ. Cреди восьми последовательных натуральных чисел найдутся числа, дающие остатки 2 и 6 при делении на 8. Они делятся на 2, но не делятся на 4, так что они обязаны иметь вид 2 k ² и 2 m ². Тогда 2 k ² – 2 m ² = 4, то есть k ² – m ² = 2, что невозможно. Противоречие.
Второй способ. Снова рассмотрим число n , дающее остаток 6 при делении на 8. Тогда n = 8 k + 6 = 2 m ², то есть m ² = 4 k + 3. Но квадрат целого числа не может давать остаток 3 при делении на 4.
Ответ
Замечания
1. Пять почти квадратов подряд идти могут, например, (1, 2, 3, 4, 5). Более того, в первом миллионе чисел таких последовательностей из пяти почти квадратов ровно 4: (1, 2, 3, 4, 5), (16, 17, 18, 19, 20); (97, 98, 99, 100, 101) и (241, 242, 243, 244, 245). Автору задачи неизвестно, могут ли идти подряд шесть или семь почти квадратов.
2. Можно показать, что почти квадраты не могут давать остатки 6, 10, 15, 21, 22, 24, 30, 33 и 34 при делении на 36. Таким образом, если найдётся 7 подряд идущих почти квадратов, то они могут давать только остатки –1, 0, 1, . 5 при делении на 36. Те среди них, что дают остатки 2 и 3, могут быть только лишь вида 2 x ² и 3 y ² соответственно, таким образом, семерка подряд идущих почти квадратов даёт решение уравнения 3 y ² – 2 x ² = 1, которое сводится к уравнению Пелля. Более того, ни одно из наших чисел 2 x ² и 3 y ² не делится на 5. Действительно, если какое-то из них делится на 5, то второе имеет вид 5 k ± 1, что невозможно для чисел вида 2 x ² и 3 y ². Значит, это два подряд идущих ненулевых остатка по модулю 5. Но 2 и 3 – квадратичные невычеты по модулю 5, а 1 и 4 – вычеты, значит, 2 x ² и 3 y ² тоже невычеты и они идут подряд. Итак, это в точности 2 и 3 по модулю 5. Отсюда получаем, что то число, кратное 36, среди найденной семерки почти квадратов делится еще и на 5, значит, то, сравнимо с 5 (mod 36), тоже делится на 5 и одно из этих двух кратных пяти чисел не делится на 25, а следовательно, имеет вид 5 z ². Таким образом, существование семи идущих подряд почти квадратов влечет за собой решение системы уравнений, сводящихся к уравнениям Пелля, а именно 3 y ² – 2 x ² = 1 и
5 z ² – 2 x ² = 3 или –2. Отметим, что у одной из этих систем (где 5 z ² – 2 x ² = 3) – есть решения, например, (1, 1, 1) или (11, 9, 7).
Источники и прецеденты использования
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Год | 2015 |
| Номер | 78 |
| класс | |
| Класс | 8 |
| задача | |
| Номер | 4 |
Что такое точный квадрат
В десятичной записи целого числа A все цифры, кроме первой и последней, нули, первая и последняя – не нули, число цифр – не меньше трёх.
Доказать, что A не является точным квадратом.
Решение
Предположим, что A точный квадрат. Тогда его последняя цифра будет 1, 4, 5, 6 или 9. Но точный квадрат не может оканчиваться ни на 05, ни на 06. Следовательно, число A оканчивается на одну из цифр 1, 4, 9. Обозначим через x квадратный корень из последней цифры числа A . Пусть k – число нулей в числе A – x ². (Можно считать, что k > 2.) Так как число x не делится на 5, то ровно одно из чисел – x , + x делится на 5, а значит, и на 5 k . Следовательно, одно из этих чисел не меньше 5 k , а другое не меньше 5 k – 6, а значит, произведение этих чисел не меньше, чем 5 k (5 k – 6) > 5 k ·9·2 k = 9·10 k , что противоречит ( k +1)-значности числа A . Итак, число A не может быть точным квадратом.
Источники и прецеденты использования
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Номер | 23 |
| Год | 1960 |
| вариант | |
| 1 | |
| Класс | 10 |
| Тур | 1 |
| задача | |
| Номер | 4 |