Решить задачу на любом языке

Question

Однажды огромный самец гориллы наткнулся на землю квадрат n × n и выложил в него n^2 бананов, в каждую клеточку по банану. Совершенно внезапно на голову горилле упал новый банан. Самец обрадовался, но не знал, куда же его деть. Недолго думая, он решил начертить новое поле размером x × y. При этом должно быть выполнено следующее:

Новое поле содержит все бананы и не содержит пустых мест (x · y = n^2 + 1);

Периметр нового поля максимальный;

Стороны нового поля должны иметь длину хотя бы 2.

Помогите огромному самцу гориллы найти подходящие размеры нового поля.

Формат входных данных

В первой строке дано целое число t — количество наборов входных данных (1 ≤ t ≤ 10^6). Далее следует описание наборов.

В единственной строке каждого набора дано целое число n (1 ≤ n ≤ 10^6) — изначальный размер поля.

Формат выходных данных

Для каждого набора входных данных выведите два числа x и y (x ≤ y) —размеры нового поля или −1, если подходящего поля не существует.

стандартный ввод стандартный вывод

3
4
13
1
-1
2 85
-1

Надо решить задачу на любом языке (желательно, на питоне), и что самое главное: обратите внимание на ограничение по времени, во входных данных может быть миллион наборов по миллиону, и это всё должно выполняться не более 2-х секунд. Тестовых данных кроме этих нет.

Моё решение (не продит по времени):

def search():
    n = int(input()) ** 2 + 1
    flag = True
    divider = 2

    while n % divider != 0:
        divider += 1
        if divider * 2 > n:
            flag = False
            break

    if n == 2:
        return -1

    if flag:
        return n // divider, divider
    else:
        return -1

for _ in range(int(input())):
    ans = search()
    if ans == -1:
        print(-1)
    else:
        x, y = ans
        print(y, x)

Answer 1

Дано натуральное n, требуется решить уравнение n² + 1 = xy в целых числах, где 2 ≤ x ≤ y, x минимальное возможное. Последнее требование – следствие максимальности периметра.

x должно быть простым. Если оно не простое, то его можно разложить в произведение и сделать новое решение у которого периметр будет больше.

Если n нечётное, то n² + 1 чётное и решение x = 2.

Если n чётное, то n² + 1 нечётное. Следовательно нужно искать минимальный нечётный простой делитель n² + 1.

Нечётные простые разбиваются на два класса 4k + 1 и 4k + 3. Есть утверждение, что n² + 1 никогда не делится на 4k + 3.

В качестве потенциальных делителей нас интересуют простые числа вида 4k + 1 не превосходящие n. Можно показать что всегда x ≤ n.

make_divs – решето Эратосфена для нечётных чисел. Возвращаются только простые вида 4k + 1. Их 39175 штук в первом миллионе. Время построения меньше одной десятой секунды.

main вводит n и ищет его делитель, последовательно проверяя кандидатов.

import math
import sys


def make_divs(n):
    sieve = bytearray(n // 2)
    sieve[0] = 1
    for p in range(3, math.isqrt(n - 1) + 1, 2):
        for i in range(p * p // 2, n // 2, p):
            sieve[i] = 1
    return [1 + 2 * i for i in range(0, n // 2, 2) if sieve[i] == 0]


def main():
    divs = make_divs(10 ** 6 + 1)

    input() # skip t
    for n in map(int, sys.stdin):
        k = n * n + 1
        if k % 2 == 0:
            if 4 <= k:
                print(2, k // 2)
            else:
                print(-1)
            continue
        for p in divs:
            if p > n:
                print(-1)
                break
            if k % p == 0:
                print(p, k // p)
                break


main()

$ echo -e "3\n4\n13\n1" | python task.py
-1
2 85
-1

Самое тяжёлое для решения n=997294:

$ time -p (echo 1; echo 997294)| python task.py
994141 1000457
real 0.04
user 0.03
sys 0.00

Тысяча примеров в секунду для n=997294:

$ time -p (echo 1000; for i in {1..1000}; do echo 997294; done) | python task.py | wc -l
1000
real 1.07
user 1.07
sys 0.01

Меньше чем за минуту можно решить все примеры до миллиона:

$ time -p (echo 1000000; seq 1 1000000) | python task.py > table.txt
real 33.64
user 33.64
sys 0.02

$ head table.txt
-1
-1
2 5
-1
2 13
-1
2 25
5 13
2 41
-1

$ tail table.txt
2 499991000041
5 199996800013
2 499993000025
13 76922153849
2 499995000013
2749 363765733
2 499997000005
5 199999200001
2 499999000001
73 13698630137

P.S. Задача упомянута в Т-Поколение 2024-2025. Параллель C. Донабор. Смутно помню, что задачи от "Т" отличаются некоторой кривизной постановки.

P.P.S. https://oeis.org/A002314 связана с делителями n² + 1. С её помощью можно составить таблицу с решениями, но я не знаю эффективного алгоритма вычисления A002314. Есть красивая формула с факториалом, но счёт по ней долгий.

P.P.P.S. Вариант на C++ в среднем в десять раз быстрее Питона. Тоже в две секунды не уложиться. Остаётся надеяться, что проверяющая система не содержит большие тесты со сложными n.

P.P.P.P.S. При объёмном вводе for line in sys.stdin: заметно быстрее цикла с input().

БЛОГ НА HUSL

Решить задачу на любом языке

Ответы (1 шт):