Comprobar si el cuadrado de un número es divisible por K o no

Dados dos enteros, X y K , la tarea es encontrar si X ² es divisible por K o no. Aquí, tanto K como X pueden estar en el rango [1,10 ¹⁸ ] .

Ejemplos:  

Entrada: X = 6, K = 9 
Salida: SI 
Explicación: 
Dado que 6 ² es igual a 36, ​​que es divisible por 9.

Entrada: X = 7, K = 21 
Salida: NO 
Explicación: 
Dado que 7 ² es igual a 49, que no es divisible por 21. 
 

Enfoque: 
como se mencionó anteriormente, X puede estar en el rango [1,10 ¹⁸ ] , por lo que no podemos verificar directamente si X ² es divisible por K o no, ya que puede causar un desbordamiento de memoria. Por lo tanto , el enfoque eficiente es calcular primero el Máximo Común Divisor de X y K. Después de calcular el MCD , lo tomaremos como la porción máxima que podemos dividir entre X y K. Reduzca K por GCD y verifique si X es divisible por K reducido o no.

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

// C++ implementation to
// check if the square of X is
// divisible by K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return if
// square of X is divisible
// by K
void checkDivisible(int x, int k)
{
    // Finding gcd of x and k
    int g = __gcd(x, k);
 
    // Dividing k by their gcd
    k /= g;
 
    // Check for divisibility of X
    // by reduced K
    if (x % k == 0) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
}
 
// Driver Code
int main()
{
    int x = 6, k = 9;
    checkDivisible(x, k);
 
    return 0;
}

// Java implementation to
// check if the square of X is
// divisible by K
 
class GFG{
 
// Function to return if
// square of X is divisible
// by K
static void checkDivisible(int x, int k)
{
    // Finding gcd of x and k
    int g = __gcd(x, k);
 
    // Dividing k by their gcd
    k /= g;
 
    // Check for divisibility of X
    // by reduced K
    if (x % k == 0)
    {
        System.out.print("YES\n");
    }
    else
    {
        System.out.print("NO\n");
    }
}
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver Code
public static void main(String[] args)
{
    int x = 6, k = 9;
    checkDivisible(x, k);
}
}
 
// This code is contributed by gauravrajput1

# Python3 implementation to
# check if the square of X is
# divisible by K
 
from math import gcd
 
# Function to return if
# square of X is divisible
# by K
def checkDivisible(x, k):
     
    # Finding gcd of x and k
    g = gcd(x, k)
 
    # Dividing k by their gcd
    k //= g
 
    # Check for divisibility of X
    # by reduced K
    if (x % k == 0):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
     
    x = 6
    k = 9
    checkDivisible(x, k);
     
# This code is contributed by Bhupendra_Singh

// C# implementation to check
// if the square of X is
// divisible by K
using System;
 
class GFG{
 
// Function to return if
// square of X is divisible
// by K
static void checkDivisible(int x, int k)
{
     
    // Finding gcd of x and k
    int g = __gcd(x, k);
 
    // Dividing k by their gcd
    k /= g;
 
    // Check for divisibility of X
    // by reduced K
    if (x % k == 0)
    {
        Console.Write("YES\n");
    }
    else
    {
        Console.Write("NO\n");
    }
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver Code
public static void Main(String[] args)
{
    int x = 6, k = 9;
     
    checkDivisible(x, k);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript implementation to
// check if the square of X is
// divisible by K
 
// Return gcd of two numbers
function gcd(a, b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
// Function to return if
// square of X is divisible
// by K
function checkDivisible(x, k)
{
     
    // Finding gcd of x and k
    var g = gcd(x, k);
 
    // Dividing k by their gcd
    k /= g;
 
    // Check for divisibility of X
    // by reduced K
    if (x % k == 0)
    {
        document.write("YES");
    }
    else
    {
        document.write("NO");
    }
}
 
// Driver code
var x = 6, k = 9;
checkDivisible(x, k);
 
// This code is contributed by Ankita saini
    
</script>

YES

Complejidad del tiempo: O(log(max(x, k)))

Espacio Auxiliar;:O(1)