Dado un número entero N , la tarea es verificar si N tiene un número impar de divisores impares y un número par de divisores pares.
Ejemplos :
Entrada: N = 36
Salida: Sí
Explicación:
Divisores de 36 = 1, 2, 3, 4, 6, 9, 12, 18, 36
Número de divisores impares (1, 3, 9) = 3 [Impar] Número
de pares Divisores(2, 4, 6, 12, 18, 36) = 6 [Par]Entrada: N = 28
Salida: No
Enfoque ingenuo : la idea es encontrar los factores del número N y contar los factores impares de N y los factores pares de N. Finalmente, verifique si el conteo de factores impares es impar y el conteo de factores pares es par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
// Function to find the count
// of even and odd factors of N
void checkFactors(lli N)
{
lli ev_count = 0, od_count = 0;
// Loop runs till square root
for (lli i = 1;
i <= sqrt(N) + 1; i++) {
if (N % i == 0) {
if (i == N / i) {
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
else {
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
if ((N / i) % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
}
}
// Condition to check if the even
// factors of the number N is
// is even and count of
// odd factors is odd
if (ev_count % 2 == 0
&& od_count % 2 == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
lli N = 36;
checkFactors(N);
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
// Function to find the count
// of even and odd factors of N
static void checkFactors(long N)
{
long ev_count = 0, od_count = 0;
// Loop runs till square root
for(long i = 1;
i <= Math.sqrt(N) + 1; i++)
{
if (N % i == 0)
{
if (i == N / i)
{
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
else
{
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
if ((N / i) % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
}
}
// Condition to check if the even
// factors of the number N is
// is even and count of
// odd factors is odd
if (ev_count % 2 == 0 && od_count % 2 == 1)
System.out.print("Yes" + "\n");
else
System.out.print("No" + "\n");
}
// Driver Code
public static void main(String[] args)
{
long N = 36;
checkFactors(N);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation of the
# above approach
# Function to find the count
# of even and odd factors of N
def checkFactors(N):
ev_count = 0; od_count = 0;
# Loop runs till square root
for i in range(1, int(pow(N, 1 / 2)) + 1):
if (N % i == 0):
if (i == N / i):
if (i % 2 == 0):
ev_count += 1;
else:
od_count += 1;
else:
if (i % 2 == 0):
ev_count += 1;
else:
od_count += 1;
if ((N / i) % 2 == 0):
ev_count += 1;
else:
od_count += 1;
# Condition to check if the even
# factors of the number N is
# is even and count of
# odd factors is odd
if (ev_count % 2 == 0 and
od_count % 2 == 1):
print("Yes" + "");
else:
print("No" + "");
# Driver Code
if __name__ == '__main__':
N = 36;
checkFactors(N);
# This code is contributed by Princi Singh
C#
// C# implementation of the
// above approach
using System;
class GFG{
// Function to find the count
// of even and odd factors of N
static void checkFactors(long N)
{
long ev_count = 0, od_count = 0;
// Loop runs till square root
for(long i = 1;
i <= Math.Sqrt(N) + 1; i++)
{
if (N % i == 0)
{
if (i == N / i)
{
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
else
{
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
if ((N / i) % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
}
}
// Condition to check if the even
// factors of the number N is
// is even and count of
// odd factors is odd
if (ev_count % 2 == 0 && od_count % 2 == 1)
Console.Write("Yes" + "\n");
else
Console.Write("No" + "\n");
}
// Driver Code
public static void Main(String[] args)
{
long N = 36;
checkFactors(N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation of the
// above approach
// Function to find the count
// of even and odd factors of N
function checkFactors(N)
{
let ev_count = 0, od_count = 0;
// Loop runs till square root
for (let i = 1;
i <= Math.sqrt(N) + 1; i++) {
if (N % i == 0) {
if (i == Math.floor(N / i)) {
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
else {
if (i % 2 == 0)
ev_count += 1;
else
od_count += 1;
if (Math.floor(N / i) % 2 == 0)
ev_count += 1;
else
od_count += 1;
}
}
}
// Condition to check if the even
// factors of the number N is
// is even and count of
// odd factors is odd
if (ev_count % 2 == 0
&& od_count % 2 == 1)
document.write("Yes" + "<br>");
else
document.write("No" + "<br>");
}
// Driver Code
let N = 36;
checkFactors(N);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
Yes
Complejidad de tiempo: O(N (1/2) )
Espacio Auxiliar: O(1)
Enfoque eficiente : la observación clave en el problema es que el número de divisores impares es impar y el número de divisores pares es par solo en el caso de cuadrados perfectos. Por lo tanto, la mejor solución sería verificar si el número dado es un cuadrado perfecto o no . Si es un cuadrado perfecto, escriba «Sí»; de lo contrario, escriba «No».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
// Function to check if the
// number is a perfect square
bool isPerfectSquare(long double x)
{
long double sr = sqrt(x);
// If square root is an integer
return ((sr - floor(sr)) == 0);
}
// Function to check
// if count of even divisors is even
// and count of odd divisors is odd
void checkFactors(lli N)
{
if (isPerfectSquare(N))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
lli N = 36;
checkFactors(N);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
// Function to check if the
// number is a perfect square
static boolean isPerfectSquare(double x)
{
// Find floating point value of
// square root of x.
double sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function to check if count of
// even divisors is even and count
// of odd divisors is odd
static void checkFactors(int x)
{
if (isPerfectSquare(x))
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int N = 36;
checkFactors(N);
}
}
// This code is contributed by dewantipandeydp
Python3
# Python3 implementation of the above approach
import math
# Function to check if the
# number is a perfect square
def isPerfectSquare(x):
# Find floating povalue of
# square root of x.
sr = pow(x, 1 / 2);
# If square root is an integer
return ((sr - math.floor(sr)) == 0);
# Function to check if count of
# even divisors is even and count
# of odd divisors is odd
def checkFactors(x):
if (isPerfectSquare(x)):
print("Yes");
else:
print("No");
# Driver code
if __name__ == '__main__':
N = 36;
checkFactors(N);
# This code is contributed by sapnasingh4991
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to check if the
// number is a perfect square
static bool isPerfectSquare(double x)
{
// Find floating point value of
// square root of x.
double sr = Math.Sqrt(x);
// If square root is an integer
return ((sr - Math.Floor(sr)) == 0);
}
// Function to check if count of
// even divisors is even and count
// of odd divisors is odd
static void checkFactors(int x)
{
if (isPerfectSquare(x))
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main(String[] args)
{
int N = 36;
checkFactors(N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation of the
// above approach
// Function to check if the
// number is a perfect square
function isPerfectSquare(x)
{
sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function to check
// if count of even divisors is even
// and count of odd divisors is odd
function checkFactors(N)
{
if (isPerfectSquare(N))
document.write("Yes" + "<br>");
else
document.write("No" + "<br>");
}
// Driver Code
N = 36;
checkFactors(N);
// This code is contributed by Mayank Tyagi
</script>
Producción:
Yes
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)