Recuento de divisores de Fibonacci de un número dado

Dado un número N , la tarea es encontrar el número de divisores de N que pertenecen a la serie de Fibonacci . 

Ejemplos: 

Entrada: N = 12 
Salida: 3 
Explicación: 
1, 2 y 3 son los 3 divisores de 12 que están en la serie de Fibonacci. 
Por lo tanto, la respuesta es 3.

Entrada: N = 110 
Salida: 4 
Explicación: 
1, 2, 5 y 55 son 4 divisores de 110 que están en la serie de Fibonacci. 
 

Enfoque eficiente : 

1. Cree una tabla hash para almacenar todos los números de Fibonacci hasta N, para verificar el tiempo O (1).
2. Encuentra todos los divisores de N en O(∛N)
3. Para cada divisor, verifica si también es un número de Fibonacci. Cuente el número de dichos divisores e imprímalos.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to count number of divisors
// of N which are Fibonacci numbers
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to create hash table
// to check Fibonacci numbers
void createHash(
    set<int>& hash, int maxElement)
{
    int prev = 0, curr = 1;
    hash.insert(prev);
    hash.insert(curr);
 
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.insert(temp);
        prev = curr;
        curr = temp;
    }
}
 
// Function to count number of divisors
// of N which are fibonacci numbers
int countFibonacciDivisors(int n)
{
    set<int> hash;
    createHash(hash, n);
 
    int cnt = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
 
            // If divisors are equal,
            // check and count only one
            if ((n / i == i)
                && (hash.find(n / i)
                    != hash.end()))
                cnt++;
 
            // Otherwise check and count both
            else {
                if (hash.find(n / i)
                    != hash.end())
                    cnt++;
                if (hash.find(n / (n / i))
                    != hash.end())
                    cnt++;
            }
        }
    }
    return cnt;
}
 
// Driver code
int main()
{
    int n = 12;
 
    cout << countFibonacciDivisors(n);
 
    return 0;
}

// Java program to count number of divisors
// of N which are Fibonacci numbers
import java.util.*;
 
class GFG{
  
// Function to create hash table
// to check Fibonacci numbers
static void createHash(
    HashSet<Integer> hash, int maxElement)
{
    int prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
  
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
  
// Function to count number of divisors
// of N which are fibonacci numbers
static int countFibonacciDivisors(int n)
{
    HashSet<Integer> hash = new HashSet<Integer>();
    createHash(hash, n);
  
    int cnt = 0;
    for (int i = 1; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
  
            // If divisors are equal,
            // check and count only one
            if ((n / i == i)
                && (hash.contains(n / i)))
                cnt++;
  
            // Otherwise check and count both
            else {
                if (hash.contains(n / i))
                    cnt++;
                if (hash.contains(n / (n / i)))
                    cnt++;
            }
        }
    }
    return cnt;
}
  
// Driver code
public static void main(String[] args)
{
    int n = 12;
  
    System.out.print(countFibonacciDivisors(n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to count number of divisors
# of N which are Fibonacci numbers
from math import sqrt,ceil,floor
 
# Function to create hash table
# to check Fibonacci numbers
def createHash(maxElement):
    prev = 0
    curr = 1
    d = dict()
    d[prev] = 1
    d[curr] = 1
 
    while (curr <= maxElement):
        temp = curr + prev
        d[temp] = 1
        prev = curr
        curr = temp
    return d
 
# Function to count number of divisors
# of N which are fibonacci numbers
def countFibonacciDivisors(n):
    hash = createHash(n)
 
    cnt = 0
    for i in range(1, ceil(sqrt(n))):
        if (n % i == 0):
 
            # If divisors are equal,
            # check and count only one
            if ((n // i == i)
                and (n // i in hash)):
                cnt += 1
 
            # Otherwise check and count both
            else:
                if (n // i in hash):
                    cnt += 1
                if (n // (n // i) in hash):
                    cnt += 1
    return cnt
 
# Driver code
n = 12
 
print(countFibonacciDivisors(n))
 
# This code is contributed by mohit kumar 29

// C# program to count number of divisors
// of N which are Fibonacci numbers
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to create hash table
// to check Fibonacci numbers
static void createHash(
    HashSet<int> hash, int maxElement)
{
    int prev = 0, curr = 1;
    hash.Add(prev);
    hash.Add(curr);
   
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.Add(temp);
        prev = curr;
        curr = temp;
    }
}
   
// Function to count number of divisors
// of N which are fibonacci numbers
static int countFibonacciDivisors(int n)
{
    HashSet<int> hash = new HashSet<int>();
    createHash(hash, n);
   
    int cnt = 0;
    for (int i = 1; i <= Math.Sqrt(n); i++) {
        if (n % i == 0) {
   
            // If divisors are equal,
            // check and count only one
            if ((n / i == i)
                && (hash.Contains(n / i)))
                cnt++;
   
            // Otherwise check and count both
            else {
                if (hash.Contains(n / i))
                    cnt++;
                if (hash.Contains(n / (n / i)))
                    cnt++;
            }
        }
    }
    return cnt;
}
   
// Driver code
public static void Main(String[] args)
{
    int n = 12;
   
    Console.Write(countFibonacciDivisors(n));
}
}
  
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to count number of divisors
// of N which are Fibonacci numbers
 
// Function to create hash table
// to check Fibonacci numbers
function createHash( hash, maxElement)
{
    let prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
  
    while (curr <= maxElement) {
        let temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
  
// Function to count number of divisors
// of N which are fibonacci numbers
function countFibonacciDivisors(n)
{
    let hash = new Set();
    createHash(hash, n);
  
    let cnt = 0;
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
  
            // If divisors are equal,
            // check and count only one
            if ((n / i == i)
                && (hash.has(n / i)))
                cnt++;
  
            // Otherwise check and count both
            else {
                if (hash.has(n / i))
                    cnt++;
                if (hash.has(n / (n / i)))
                    cnt++;
            }
        }
    }
    return cnt;
}
 
// Driver Code
 
    let n = 12;
  
    document.write(countFibonacciDivisors(n));
 
</script>

3

Complejidad de tiempo: O(∛N)

Espacio Auxiliar: O(N)