Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Простые пары

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

Пусть M некоторое натуральное число. Обозначим как Pair(M) множество всех пар натуральных чисел (a, b), a ≤ b таких, что a + b = M .

Пусть n ≥ 2 некоторое натуральное число. Обозначим как Prime(n) множество всех простых чисел из отрезка [2, n] (натуральное число называется простым, если оно делится только на единицу и на само себя).

Будем говорить, что пара чисел (a, b) лексикографически меньше пары чисел (c, d), если a < c или a = c, а b < d.

Пусть задано число n. Упорядочим все пары, входящие в хотя бы одно из множеств Pair(P) при P ∈ Prime(n), лексикографически. Ваша задача найти k-ую пару в этом порядке.

Входные данные

Входной файл INPUT.TXT содержит два целых числа: n и k (2 ≤ n ≤ 106, 1 ≤ k ≤ 1018).

Выходные данные

В выходной файл OUTPUT.TXT выведите числа a и b, образующие искомую пару. Если соответствующей пары не существует (то есть число k слишком большое), выведите в выходной файл -1 -1.

Примеры

INPUT.TXTOUTPUT.TXT
110 21 2
210 10000000000-1 -1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 A. Бисер
 B. Апельсины - 2
 C. Простые пары
 D. Произведения на отрезках

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483