703720. Count divisors of product of array elements
Medium
Count Divisors of Product of Array Elements
Summary
Given an array of integers, count the number of divisors for the product of all elements in the array. The problem involves arrays and prime numbers.
Detailed Explanation
To solve this problem, we will first calculate the product of all elements in the array. Then, we will find the divisors for this product. A divisor is a number that can be divided by another number without leaving a remainder. To efficiently count the divisors, we will use the concept of prime factorization.
Here's a step-by-step breakdown of the solution:
- Calculate the product of all elements in the array.
- Find the prime factors of this product using a prime factorization algorithm (e.g., trial division or Sieve of Eratosthenes).
- For each prime factor, calculate its exponents in the prime factorization.
- Use these exponents to count the number of divisors for the product.
Optimized Solutions
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long product = 1;
for (int i = 0; i < n; i++) {
product *= scanner.nextInt();
}
int count = countDivisors(product);
System.out.println(count);
}
public static int countDivisors(long product) {
int count = 1;
long p = 2;
while (p * p <= product) {
int power = 0;
while (product % p == 0) {
product /= p;
power++;
}
if (power > 0) {
for (int i = 0; i <= power; i++) {
count++;
}
}
p++;
}
if (product > 1) {
count += 2;
} else if (product == 1) {
count = 1;
}
return count;
}
}