Watson gives an integer \(N\) to Sherlock and asks him: What is the number of divisors of \(N\) that are divisible by 2?
Input Format
First line contains \(T\), the number of testcases. This is followed by \(T\) lines each containing an integer \(N\).
Output Format
For each testcase, print the required answer in one line.
Constraints
- \(1\leq T\leq 100\)
- \(1\leq N\leq 10^9\)
Solution
When writing a number \(N\) as the product of its prime factors, we have \(N = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\dots\). From which the number of divisors follows as \(d(N) = (e_1+1)(e_2+1)(e_3+1)\dots\)
From the general case we have to count only the numbers that are divisible by 2. We have two cases for \(p_k=2\):
1) if \(e_k=0\) then the result must be zero, as no factor of 2 is present
2) if \(e_k\neq 0\) then we know that at least one factor of 2 is present. Since we want to know the number of divisors of \(N\) that are divisible by 2, we factor out 2 to say \(N=2M\). Calculating the number of divisors \(d(M)\) is then just \(d(M)=e_k (e_1+1)(e_2+1)\dots\)
Since \(p_i\equiv1\pmod{2}\) for all \(p_i\neq 2\), we can use this to avoid branching completely like so, using Rubys prime factorization library:
def divisors(n)
Prime.prime_division(n).inject(1) {|s, k|
s * (k[1] + k[0] % 2) * (1 - k[0] % 2)
}
end