Page Contents

## Problem Statement

Alice has learnt factorization recently. Bob doesn’t think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of N numbers. Alice is frightened of big numbers and hence is asking you for help. Your task is simple. Given N numbers, you need to tell the number of distinct factors of the product of these N numbers.

## Input

First line of input contains a single integer **T**, the number of test cases.

Each test starts with a line containing a single integer **N**.

The next line consists of **N** space separated integers (**A _{i}**).

## Output

For each test case,

## Constraints

1 ≤T≤ 100

1 ≤N≤ 10

2 ≤A≤ 1000000_{i}

## Example

Input:

3

3

3 5 7

3

2 4 6

2

5 5Output:

8

10

3

## Solution

There can be two Good Approaches to this problem:

- Use Bitwise Operators (Hybrid way)😇.
**Best Approach** - Use any Sieve to find Primes (Normal Way).

Let’s Code them one-by-one. In case you face any problem, feel free to comment down below. I shall be happy to help.

### The Bitwise way:

This approach can be a little tricky and hard to think one the first go. But with good

#### Approach

- Find the number of factors the given numbers have.
- Save the number of factors in a list.
- Suppose a number has these factors -> [2, 2, 2, 3, 3, 5]
- Then the total number that can be generated from the list is given as (3+1)*(2+1)*(1+1) = 24

Our major target should be to find number of factors as quickly as possible.

#### Code

import sys fac = [] T = int(input()) def factors(n): count = 0 # check if a number is even and count number of 2's while n & 1 == 0: # Equivalent to //ing by 2 n >>= 1 count += 1 # append into factor list if count: fac.append((2,count)) # starting from 3 with a step of 2 till root of 'n' for i in range(3,int(n**.5)+1,2): count = 0 while n % i == 0: count += 1 n /= i if count: fac.append((i,count)) # include the last factor if n > 2: fac.append((n,1)) while T: # initialize the factor list for every test cases fac = [] N = int(input()) L = list(map(int, sys.stdin.readline().split())) for i in L: factors(i) # sort the factor list for optimization fac.sort() len_factor_list = len(fac) su = 0 result = 1 num = fac[0][0] i = 0 # number of factor => 12 ->[(2,2), (3,1)] --> (2+1)*(1+1) while i < len_factor_list: su = 0 while i < len_factor_list and fac[i][0] == num: su += fac[i][1] i += 1 result *= (su+1) if i < len_factor_list: num = fac[i][0] print(result) T -= 1

### The Normal Way

#### Code

import sys # get all the primes less than 1000000 def getPrime(): primes = [] # initialize the array arr = [0]*1000001 for i in range(2, 1000001): if arr[i] != 1: # set all the multiples of prime to 1 j = i * 2 while j <= 1000000: arr[j] = 1 j += i for i in range(2, len(arr)): # indexes with value zero are the primes if arr[i] == 0: primes.append(i) return primes # calculate the factors def getFactors(factors, primes, n): k = n for x in primes: # if n is divisible by x increase the value at key == x by 1 if x > k: break while n % x == 0 and n >= x: if x in factors: factors[x] += 1 else: factors[x] = 1 n /= x return factors # calculate primes primes = getPrime() t = int(sys.stdin.readline()) while t: n = int(sys.stdin.readline()) factors = dict() arr = list(map(int, sys.stdin.readline().split())) res = 1 for x in arr: factors = getFactors(factors, primes, x) for key, value in factors.items(): # number of factor => 12 ->[(2,2), (3,1)] --> (2+1)*(1+1) res *= (value + 1) print(res) t -= 1