Count of Fibonacci pairs which satisfy the given equation | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define size  10001 NEW_LINE using namespace std ; long long fib [ 100010 ] ; int freq [ 100010 ] ; bool isPerfectSquare ( int x ) { int s = sqrt ( x ) ; return ( s * s == x ) ; } int isFibonacci ( int n ) { if ( isPerfectSquare ( 5 * n * n + 4 ) || isPerfectSquare ( 5 * n * n - 4 ) ) return 1 ; return 0 ; } void compute ( int a , int b ) { for ( int i = 1 ; i < 100010 ; i ++ ) { fib [ i ] = isFibonacci ( i ) ; } for ( int x = 1 ; x < 100010 ; x ++ ) { for ( int y = 1 ; y < size ; y ++ ) { if ( fib [ x ] == 1 && fib [ y ] == 1 && a * x + b * y < 100010 ) { freq [ a * x + b * y ] ++ ; } } } } int main ( ) { int Q = 2 , A = 5 , B = 10 ; compute ( A , B ) ; int arr [ Q ] = { 50 , 150 } ; for ( int i = 0 ; i < Q ; i ++ ) { cout << freq [ arr [ i ] ] << " ▁ " ; } return 0 ; }