Dado un número entero N , la tarea es contar el número de formas en que N se puede expresar como un exponente, es decir, x y , donde xey son números enteros positivos.
Ejemplos:
Entrada: N = 64
Salida: 4
Explicación: 64 se puede expresar como 2 6 , 4 3 , 8 2 y 64 1Entrada: N = 27
Salida: 2
Enfoque: La idea para resolver el problema dado es encontrar la descomposición en factores primos del número N y luego, encontrar el número de factores primos del MCD de los exponentes de los factores primos del número N dado .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate GCD of a
// and b using Euclidean Algorithm
long long int gcd(long long int a,
long long int b)
{
// Iterate until b is non-zero
while (b > 0) {
long long int rem = a % b;
a = b;
b = rem;
}
// Return the GCD
return a;
}
// Function to count the number of
// ways N can be expressed as x^y
int countNumberOfWays(long long int n)
{
// Base Case
if (n == 1)
return -1;
// Stores the gcd of powers
long long int g = 0;
int power = 0;
// Calculate the degree of 2 in N
while (n % 2 == 0) {
power++;
n /= 2;
}
g = gcd(g, power);
// Calculate the degree of prime numbers in N
for (int i = 3; i <= sqrt(n); i += 2) {
power = 0;
// Calculate the degree of
// prime 'i' in N
while (n % i == 0) {
power++;
n /= i;
}
g = gcd(g, power);
}
// If N is a prime, g becomes 1.
if (n > 2)
g = gcd(g, 1);
// Stores the number of ways
// to represent N as x^y
int ways = 1;
// Find the number of Factors of g
power = 0;
while (g % 2 == 0) {
g /= 2;
power++;
}
// Update the count of ways
ways *= (power + 1);
// Iterate to find rest of the prime numbers
for (int i = 3; i <= sqrt(g); i += 2) {
power = 0;
// Find the power of i
while (g % i == 0) {
power++;
g /= i;
}
// Update the count of ways
ways *= (power + 1);
}
// If g is prime
if (g > 2)
ways *= 2;
// Return the total number of ways
return ways;
}
// Driver Code
int main()
{
int N = 64;
cout << countNumberOfWays(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to calculate GCD of a
// and b using Euclidean Algorithm
static int gcd(int a,
int b)
{
// Iterate until b is non-zero
while (b > 0) {
int rem = a % b;
a = b;
b = rem;
}
// Return the GCD
return a;
}
// Function to count the number of
// ways N can be expressed as x^y
static int countNumberOfWays(int n)
{
// Base Case
if (n == 1)
return -1;
// Stores the gcd of powers
int g = 0;
int power = 0;
// Calculate the degree of 2 in N
while (n % 2 == 0) {
power++;
n /= 2;
}
g = gcd(g, power);
// Calculate the degree of prime numbers in N
for (int i = 3; i <= (int)Math.sqrt(n); i += 2) {
power = 0;
// Calculate the degree of
// prime 'i' in N
while (n % i == 0) {
power++;
n /= i;
}
g = gcd(g, power);
}
// If N is a prime, g becomes 1.
if (n > 2)
g = gcd(g, 1);
// Stores the number of ways
// to represent N as x^y
int ways = 1;
// Find the number of Factors of g
power = 0;
while (g % 2 == 0) {
g /= 2;
power++;
}
// Update the count of ways
ways *= (power + 1);
// Iterate to find rest of the prime numbers
for (int i = 3; i <= (int)Math.sqrt(g); i += 2) {
power = 0;
// Find the power of i
while (g % i == 0) {
power++;
g /= i;
}
// Update the count of ways
ways *= (power + 1);
}
// If g is prime
if (g > 2)
ways *= 2;
// Return the total number of ways
return ways;
}
// Driver Code
public static void main(String[] args)
{
int N = 64;
System.out.print(countNumberOfWays(N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach import math # Function to calculate GCD of a # and b using Euclidean Algorithm def gcd(a, b) : # Iterate until b is non-zero while (b > 0) : rem = a % b a = b b = rem # Return the GCD return a # Function to count the number of # ways N can be expressed as x^y def countNumberOfWays(n) : # Base Case if (n == 1) : return -1 # Stores the gcd of powers g = 0 power = 0 # Calculate the degree of 2 in N while (n % 2 == 0) : power += 1 n //= 2 g = gcd(g, power) # Calculate the degree of prime numbers in N for i in range(3, int(math. sqrt(g)) + 1, 2): power = 0 # Calculate the degree of # prime 'i' in N while (n % i == 0) : power += 1 n //= i g = gcd(g, power) # If N is a prime, g becomes 1. if (n > 2) : g = gcd(g, 1) # Stores the number of ways # to represent N as x^y ways = 1 # Find the number of Factors of g power = 0 while (g % 2 == 0) : g //= 2 power += 1 # Update the count of ways ways *= (power + 1) # Iterate to find rest of the prime numbers for i in range(3, int(math. sqrt(g)) + 1, 2): power = 0 # Find the power of i while (g % i == 0) : power += 1 g /= i # Update the count of ways ways *= (power + 1) # If g is prime if (g > 2) : ways *= 2 # Return the total number of ways return ways # Driver Code N = 64 print(countNumberOfWays(N)) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to calculate GCD of a
// and b using Euclidean Algorithm
static int gcd(int a,
int b)
{
// Iterate until b is non-zero
while (b > 0)
{
int rem = a % b;
a = b;
b = rem;
}
// Return the GCD
return a;
}
// Function to count the number of
// ways N can be expressed as x^y
static int countNumberOfWays(int n)
{
// Base Case
if (n == 1)
return -1;
// Stores the gcd of powers
int g = 0;
int power = 0;
// Calculate the degree of 2 in N
while (n % 2 == 0)
{
power++;
n /= 2;
}
g = gcd(g, power);
// Calculate the degree of prime numbers in N
for (int i = 3; i <= (int)Math.Sqrt(n); i += 2)
{
power = 0;
// Calculate the degree of
// prime 'i' in N
while (n % i == 0)
{
power++;
n /= i;
}
g = gcd(g, power);
}
// If N is a prime, g becomes 1.
if (n > 2)
g = gcd(g, 1);
// Stores the number of ways
// to represent N as x^y
int ways = 1;
// Find the number of Factors of g
power = 0;
while (g % 2 == 0)
{
g /= 2;
power++;
}
// Update the count of ways
ways *= (power + 1);
// Iterate to find rest of the prime numbers
for (int i = 3; i <= (int)Math.Sqrt(g); i += 2)
{
power = 0;
// Find the power of i
while (g % i == 0)
{
power++;
g /= i;
}
// Update the count of ways
ways *= (power + 1);
}
// If g is prime
if (g > 2)
ways *= 2;
// Return the total number of ways
return ways;
}
// Driver Code
public static void Main(String[] args)
{
int N = 64;
Console.Write(countNumberOfWays(N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to calculate GCD of a
// and b using Euclidean Algorithm
function gcd(a, b)
{
// Iterate until b is non-zero
while (b > 0) {
let rem = a % b;
a = b;
b = rem;
}
// Return the GCD
return a;
}
// Function to count the number of
// ways N can be expressed as x^y
function countNumberOfWays(n)
{
// Base Case
if (n == 1)
return -1;
// Stores the gcd of powers
let g = 0;
let power = 0;
// Calculate the degree of 2 in N
while (n % 2 == 0) {
power++;
n /= 2;
}
g = gcd(g, power);
// Calculate the degree of prime numbers in N
for (let i = 3; i <= Math.sqrt(n); i += 2) {
power = 0;
// Calculate the degree of
// prime 'i' in N
while (n % i == 0) {
power++;
n /= i;
}
g = gcd(g, power);
}
// If N is a prime, g becomes 1.
if (n > 2)
g = gcd(g, 1);
// Stores the number of ways
// to represent N as x^y
let ways = 1;
// Find the number of Factors of g
power = 0;
while (g % 2 == 0) {
g /= 2;
power++;
}
// Update the count of ways
ways *= (power + 1);
// Iterate to find rest of the prime numbers
for (let i = 3; i <= Math.sqrt(g); i += 2) {
power = 0;
// Find the power of i
while (g % i == 0) {
power++;
g /= i;
}
// Update the count of ways
ways *= (power + 1);
}
// If g is prime
if (g > 2)
ways *= 2;
// Return the total number of ways
return ways;
}
// Driver Code
let N = 64;
document.write(countNumberOfWays(N));
</script>
Producción:
4
Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por suman_1729 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA