Задача 47: Хитрющая строка. По мотивам
ICL-2002
Михаил Густокашин
В моем классе
учится один парень - Ариф, который часто занимается на уроках
математики в общем то математикой, но не совсем той, которой надо:
то он выписывает в столбик квадраты всех чисел, то все степени
двойки, то таблицу умножения до 100*100, короче говоря, наш Ариф -
<кадр> еще тот. Недавно получил 2 за контрольную, потому что на всех
предыдущих уроках занимался далеко не тем, чем надо. Однажды он
придумал себе новое развлечение - стал выписывать в строку (без
пробелов) четвертые степени всех простых чисел подряд. У него
получилась примерно такая строка:
16816252401...
Потом ему стало интересно можно ли определить, какая цифра стоит на
n-ом месте в этой строке? Формулу подобрать он не смог, да наверное
ее и нету. Задача состоит в том, что несмотря на отсутствие формулы,
определить, какая цифра стоит на n-ом месте.
Входные данные:
Во входном файле input.txt содержится единственное число n (0 <
n < 25000).
Выходные данные:
В выходном файле output.txt содержится одна цифра, которая стоит
в этой строке на n-ом месте.
Пример 1:
input.txt:
1
output.txt:
1
Пример 2:
input.txt
5
output.txt
6
Решение:
Опять моя задачка. Тут есть два решения (которые придумал я
сам) - одно из них почему-то валится на 15000, а другое молотит все
подряд.
Как искать простые числа? Надо найти округленный квадратный корень
из числа и искать делители только от 2 до этого корня. Если у числа
есть делители, то половина из них меньше либо равна его квадратному
корню.
Первое решение(которое работает до 15000, почему-то): с оцениванием
длины 4 степени. Суть этого решения состоит в том, что мы оцениваем
длину 4 степени числа, для этого будем извлекать корень 4 степени из
степеней 10 и если число лежит например между sqrt(sqrt(10^6)) и
sqrt(sqrt(10^7)), включая sqrt(sqrt(10^6)), то длина его 4 степени
будет 6 десятичных знаков. Будем отнимать от данного числа n
полученное число, а в случае если длина получившейся четвертой
степени больше номера необходимого элемента, то запустим хитрую
процедуру извлечения цифры из типа данных extended. Если нам
необходимо извлечь первую цифру, то для этого надо вывести
округленный trunc'ом результат деления нашей 4 степени на 10^(кол-во
цифр в ней - 1). В противном случае найдем первую цифру, умножим ее
на 10^(кол-во цифр - 1) и отнимем полученное число от нашей 4
степени. Теперь уменьшим общее кол-во цифр и номер запрашиваемой
цифры на 1.
Второе решение(работает чуть медленнее, но зато может посчитать
практически любой член этой последовательности). Здесь используется
длинная арифметика, похожая на задачу 2^n. Алгоритм тут точно
такой же, так что опишу только те хитрости, которые надо здесь
применить. Во-первых: каждое число, которое необходимо возвести в 4
степень надо разбить на 10-тичные знаки с помощью mod и div, это
вроде бы несложно. Еще одна хитрость состоит в том, что элементы
массива будут иметь тип byte, а переменная для временной работы и
флаг переноса - типа longint. Процедура будет умножать массив на
число, чтобы найти 4 степень ее необходимо запустить 4 раза(вернее
один раз разбить число на 10-тичные знаки и три раза запустить
процедуру).
Третье решение (by Axel): длина 4 чтепени числа log(x)/log(10)
округленные вверх.
Далее
ð
