eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гипотеза Римана

Гипотеза Римана

\includegraphics{https://static.e-olymp.com/content/49/49270e28ebc371c9e6e548fe5edf6353526f0ecb.jpg} Гипотеза Римана о распределении нулей дзета-функции Римана была сформулирована Бернхардом Риманом в \textbf{1859} году. В то время как не найдено какой-либо закономерности, описывающей распределение простых чисел среди натуральных, Риман обнаружил, что количество простых чисел, не превосходящих \textbf{x}, функция распределения простых чисел, обозначаемая \textbf{(x)} --- выражается через распределение так называемых "нетривиальных нулей" дзета-функции. Дзета-функция Римана \textbf{ζ(s)} определена для всех комплексных \textbf{s ≠ 1} и имеет нули в отрицательных чётных \textbf{s = -2}, \textbf{-4}, \textbf{-6}, ..., . \includegraphics{https://static.e-olymp.com/content/d4/d40361f40767df7f7e63c276a202d2c6fdb1fb6d.jpg} \includegraphics{https://static.e-olymp.com/content/4a/4a3ce89e7076b8b735c8c6033caf399a2bed3b57.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/62/62c6871239483c1e41ffdc24039860867a46873c.jpg} \includegraphics{https://static.e-olymp.com/content/f5/f50db36e248f03daa70895d056f9b1f9869cb8e0.jpg} Из функционального уравнения и явного выражения при \textbf{Re s} > \textbf{1}, где \textbf{μ(n)} --- функция Мёбиуса, следует, что все остальные нули, называемые "нетривиальными", расположены в полосе \textbf{0} ≤ \textbf{Re s} ≤ \textbf{1} симметрично относительно так называемой "критической линии" \textbf{½+it}, \textbf{t} \textbf{R}. В свою очередь, функция Мёбиуса тесно связана с функцией Эйлера \textbf{φ(n)}, (равной количеству натуральных чисел взаимно-простых с \textbf{n} и не превосходящих его) соотношением , поэтому, для эффективного поиска "нетривиальных" нулей на больших промежутках, необходимо быстро находить локальные экстремумы следующей суммы: . Вам задан промежуток натуральных чисел \textbf{\[L, R\]}. Ваша задача найти натуральное \textbf{x}, такое что \textbf{x = arg max_\{k=L..R \}S(k)}, если таких чисел несколько, выведите минимальное. \InputFile В единственной строке заданы два числа \textbf{L} и \textbf{R} (\textbf{1} ≤ \textbf{L} ≤ \textbf{R} ≤ \textbf{2^31}), разделённые пробелом. \OutputFile \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Выведите единственное натуральное число \textbf{x} \textbf{\[L, R\]}, на котором достигается максимум функции \textbf{S}.
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
1 1
Выходные данные #1
1
Автор Олег Петров
Источник Летняя школа Севастополь 2013, Волна 2, День 6