PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, count the number of odd divisors and the number of even divisors of N.
EXPLANATION:
Simply implement exactly what the statement asks for: go through all the divisors of N, check whether each one is even or odd, and update the appropriate counter.
Since N \leq 100 you can iterate through all integers from 1 to N to check for divisibility, which will be \mathcal{O}(N) overall but still fast enough.
Alternately, you can use the fact that if d is a divisor of N, \frac{N}{d} will also be a divisor of N - which allows you to iterate till only \sqrt N and hence solve the task in \mathcal{O}(\sqrt N) instead.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(\sqrt N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
odd, even = 0, 0
for i in range(1, n+1):
if n%i == 0:
if i%2 == 0: even += 1
else: odd += 1
print(odd, even)