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

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Гіпотеза Рімана про розподілнулів дзета-функції Рімана була сформульована Бернхардом Ріманом у 1859 році. У то час як не знайдено якої-небудь закономірності, що описує розподіл простих чисел серед натуральних, Ріман виявив, що кількість простих чисел, які не перевищують x, функція розподілу простих чисел, яка позначається (x) — виражається через розподіл так званих "нетривіальних нулів" дзета-функції. Дзета-функція Рімана ζ(s) визначена для усіх комплексних s ≠ 1 і має нулі у від'ємних парних s = -2, -4, -6, ..., .

З функціонального рівняння та явного виразу при Re s > 1, де μ(n) — функція Мьобіуса, випливає, що усі інші нулі, які називаються "нетривіальними", розміщені у полосі 0Re s1 симетрично відносно так званої "критичної лінії" ½+it, tR. У свою чергу, функція Мьобіуса тісно пов'язана з функцією Ейлера φ(n), (рівною кількості натуральних чисел взаємно-простих з n і які не превищують його) співвідношенням , тому, для эфективного пошуку "нетривіальних" нулів на великих проміжках, необхідно швидко знаходити локальні екстремуми наступної суми: .

Вам задано проміжок натуральних чисел [L, R]. Ваша задача знайти натуральне x, таке що x = arg max_{k=L..R }S(k), якщо таких чисел декілька, виведіть мінімальне.

Вхідні дані

У єдиному рядку задано два числа L та R (1LR2^31), відокремлені пропуском.

Вихідні дані

Виведіть єдине натуральне число x[L, R], на якому досягається максимум функції S.

Приклад

Вхідні дані #1
1 1
Вихідні дані #1
1
Автор Олег Петров
Джерело Літня школа Севастополь 2013, Хвиля 2, День 6