Установить точность вещ. числа для определения числа Фибоначчи

Question

Задание такое Вам дается последовательность чисел. Для каждого числа определите, является ли оно числом Фибоначчи. Первая строка содержит одно число N – количество запросов. Следующие N строк содержат по одному целому числу. При этом соблюдаются следующие ограничения:

Размер каждого числа не превосходит 5000 цифр в десятичном представлении.

Wrong answer на 6 тесте. Может кто нибудь помочь, пожалуйста

import math

n = int(input())
for i in range(n):
    a = int(input())
    fib1 = ((5 * a * a - 4) ** 0.5) % 1. <= 0.1 * 10 ** (-100)
    fib2 = ((5 * a * a + 4) ** 0.5) % 1. <= 0.1 * 10 ** (-100)
    if fib1 or fib2:
        print("Yes")
    else:
        print("No")

Answer 1

Очень хороший тест состоит в том, что N является числом Фибоначчи тогда и только тогда, когда 5 N^2 + 4 или 5N^2 – 4 - это квадратное число.

во-первых

полученное число можно разложить на простые множители - кол-во различных простых множителей должно быть чётным - это 100% без всякой потери точности определение квадрата

вопрос насколько быстро можно перебрать простые множители от 2 до sqrt(5N**2 + 4) при условии, что в числе 5000 цифр

а во вторых

сравнивать квадраты лучше так:

int((5 * a * a - 4) ** 0.5)) ** 2 == (5 * a * a - 4)

тут тоже будет однозначный ответ

а еще быстрее так:

value = 5 * a * a - 4
value_sqrt = math.sqrt(value)
res1 = value_sqrt * value_sqrt == value

по возможности функцию возведения в степень лучше не использовать - она медленнее обычного умножения

в-третьих

для ускорения (если провал теста из-за скорости) лучше не вычислять сразу условия и для 5N+4 и для 5N-4, а сделать последовательно, тогда на числах можно иногда экономить в 2 раза по скорости

value = 5 * a * a - 4
value_sqrt = math.sqrt(value)
if value_sqrt * value_sqrt == value:
    print("Yes")
    continue

value = 5 * a * a + 4
value_sqrt = math.sqrt(value)
if value_sqrt * value_sqrt == value:
    print("Yes")
    continue

БЛОГ НА HUSL

Установить точность вещ. числа для определения числа Фибоначчи

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