Compruebe si un M-ésimo número de Fibonacci divide N-ésimo número de Fibonacci

Dados dos números M y N, la tarea es verificar si los números de Fibonacci M-th y N-th se dividen perfectamente entre sí o no.
Ejemplos: 
 

Entrada: M = 3, N = 6 
Salida: Sí 
F(3) = 2, F(6) = 8 y F(6) % F(3) = 0 
Entrada: M = 2, N = 9 
Salida: No

Un enfoque ingenuo será encontrar los números de Fibonacci N-th y M-th y verificar si son perfectamente divisibles o no. 
Un enfoque eficiente es utilizar la propiedad de Fibonacci para determinar el resultado. Si m divide perfectamente a n, entonces Fm _{también divide} perfectamente a Fn , de lo contrario no lo hace.
Excepción: cuando N es 2, siempre es posible ya que Fibo ₂ es 1, que divide a todos los demás números de Fibonacci. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to check if
// M-th fibonacci divides N-th fibonacci
#include <bits/stdc++.h>
using namespace std;
 
void check(int n, int m)
{
    // exceptional case for F(2)
    if (n == 2 || m == 2 || n % m == 0) {
        cout << "Yes" << endl;
    }
    // if none of the above cases,
    // hence not divisible
    else {
        cout << "No" << endl;
    }
}
 
// Driver Code
int main()
{
    int m = 3, n = 9;
    check(n, m);
 
    return 0;
}

// Java program to check
// if M-th fibonacci
// divides N-th fibonacci
import java.io.*;
 
class GFG
{
static void check(int n, int m)
{
    // exceptional case for F(2)
    if (n == 2 || m == 2 ||
        n % m == 0)
    {
        System.out.println( "Yes");
    }
     
    // if none of the above cases,
    // hence not divisible
    else
    {
        System.out.println( "No");
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int m = 3, n = 9;
    check(n, m);
}
}
 
// This code is contributed
// by anuj_67.

# Python 3 program to
# check if M-th fibonacci
# divides N-th fibonacci
 
def check(n, m):
 
    # exceptional case for F(2)
    if (n == 2 or m == 2 or
        n % m == 0) :
        print( "Yes" )
     
    # if none of the above
    # cases, hence not divisible
    else :
        print( "No" )
 
# Driver Code
m = 3
n = 9
check(n, m)
 
# This code is contributed
# by Smitha

// C# program to check
// if M-th fibonacci
// divides N-th fibonacci
using System;
 
class GFG
{
static void check(int n, int m)
{
    // exceptional case for F(2)
    if (n == 2 || m == 2 ||
        n % m == 0)
    {
         Console.WriteLine( "Yes");
    }
     
    // if none of the above cases,
    // hence not divisible
    else
    {
        Console.WriteLine( "No");
    }
}
 
// Driver Code
public static void Main ()
{
    int m = 3, n = 9;
    check(n, m);
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP program to check
// if M-th fibonacci
// divides N-th fibonacci
 
function check($n, $m)
{
    // exceptional case for F(2)
    if ($n == 2 || $m == 2 ||
        $n % $m == 0)
    {
        echo "Yes" , "\n";
    }
     
    // if none of the above cases,
    // hence not divisible
    else
    {
        echo "No" ," \n";
    }
}
 
// Driver Code
$m = 3; $n = 9;
check($n, $m);
 
// This code is contributed
// by anuj_67.
?>

<script>
 
// Javascript program to check if
// M-th fibonacci divides N-th fibonacci
 
function check(n, m)
{
    // exceptional case for F(2)
    if (n == 2 || m == 2 || n % m == 0) {
        document.write("Yes" + "<br>");
    }
    // if none of the above cases,
    // hence not divisible
    else {
        document.write("No" + "<br>");
    }
}
 
// Driver Code
  
    let m = 3, n = 9;
    check(n, m);
 
// This code is contributed by Mayank Tyagi
 
</script>

Yes

Complejidad Temporal: O(1).