Count of Fibonacci pairs which satisfy the given equation | Python program to find the count of Fibonacci pairs ( x , y ) which satisfy the equation Ax + By = N ; Array to store the Fibonacci numbers ; Array to store the number of ordered pairs ; Function to find if a number is a perfect square ; Function that returns 1 if N is non - fibonacci number else 0 ; N is Fibinacci if one of 5 * n * n + 4 or 5 * n * n - 4 or both are perferct square ; Function to store the fibonacci numbers and their frequency in form a * x + b * y ; Storing the Fibonacci numbers ; For loop to find all the possible combinations of the Fibonacci numbers ; Finding the number of ordered pairs ; Driver code ; Find the ordered pair for every query
import math NEW_LINE size = 101 NEW_LINE fib = [ 0 ] * 100010 NEW_LINE freq = [ 0 ] * ( 100010 ) NEW_LINE def isPerfectSquare ( x ) : NEW_LINE INDENT s = int ( math . sqrt ( x ) ) NEW_LINE return ( s * s ) == x NEW_LINE DEDENT def isFibonacci ( n ) : NEW_LINE INDENT if ( isPerfectSquare ( 5 * n * n + 4 ) or isPerfectSquare ( 5 * n * n - 4 ) ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT return 0 ; NEW_LINE DEDENT def compute ( a , b ) : NEW_LINE INDENT for i in range ( 1 , 100010 ) : NEW_LINE INDENT fib [ i ] = isFibonacci ( i ) NEW_LINE DEDENT for x in range ( 1 , 100010 ) : NEW_LINE INDENT for y in range ( 1 , size ) : NEW_LINE INDENT if ( fib [ x ] == 1 and fib [ y ] == 1 and a * x + b * y < 100010 ) : NEW_LINE INDENT freq [ a * x + b * y ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT Q = 2 NEW_LINE A = 5 NEW_LINE B = 10 NEW_LINE compute ( A , B ) ; NEW_LINE arr = [ 50 , 150 ] NEW_LINE for i in range ( Q ) : NEW_LINE INDENT print ( freq [ arr [ i ] ] , end = " ▁ " ) NEW_LINE DEDENT