CF 72C - Extraordinarily Nice Numbers

Rating: 1200
Tags: *special, math
Solve time: 1m 26s
Verified: yes

Solution

Problem Understanding

We are asked to determine whether a positive integer $x$ is extraordinarily nice. By the problem's definition, a number is extraordinarily nice if it has exactly the same number of even divisors as odd divisors. The input is a single integer $x$ between 1 and 1000. The output is simply "yes" if the number is extraordinarily nice, and "no" otherwise.

Looking at the constraints, $x \le 1000$ is small. This means we could consider counting divisors directly for each number without hitting performance issues. Each number $x$ has at most $\sqrt{x}$ divisors to check for factorization, and $1000 \times \sqrt{1000}$ is about 32,000 operations, trivial for a 2-second time limit. So, efficiency is not a major concern here, but a clever insight will simplify the solution dramatically.

An edge case arises with 1. Its only divisor is itself, which is odd. Therefore, 1 is not extraordinarily nice. Another subtle scenario is any power of 2: the divisors are all 1, 2, 4, etc., and counting the evens and odds requires careful attention. For example, 2 has divisors {1, 2}-one odd, one even-so it qualifies. Any odd number greater than 1 will have more odd divisors than even, because 1 is always odd, and multiplying by an odd number yields another odd divisor.

Understanding these patterns leads to a simplification: a number can only be extraordinarily nice if it is a power of 2, because only then can the even divisors “balance” the single odd divisor 1.

Approaches

A brute-force approach is to iterate through all numbers from 1 to $x$, check if each is a divisor of $x$, and count how many are even and how many are odd. This method is simple and correct. For $x=1000$, the worst-case operation count is roughly the number of divisors, which is about 32 in practice for numbers under 1000. While feasible, the approach does extra work: we don't need the exact list of divisors, only the pattern of evens and odds.

The key insight is to factor $x$ as $2^k \cdot m$ where $m$ is odd. The odd divisors come entirely from $m$ (including 1), while the even divisors come from multiplying powers of 2 with divisors of $m$. For the number of even divisors to equal the number of odd divisors, $m$ must be 1. This reduces the problem to checking whether $x$ is a power of 2, a simple operation using repeated division by 2.

This observation transforms a brute-force counting problem into a straightforward check using division or bitwise operations. The elegance here is recognizing the structural property of divisors: powers of 2 alone can satisfy the "extraordinarily nice" condition.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(√x)	O(1)	Accepted for this problem, but unnecessary
Power-of-2 Check	O(log x)	O(1)	Optimal, elegant, accepted

Algorithm Walkthrough

Read the integer $x$. This is the number we need to test.
Initialize a temporary variable $y = x$. This avoids modifying the input.
Repeatedly divide $y$ by 2 while it is even. Each division strips off one factor of 2.
After the loop, check if $y$ equals 1. If it does, $x$ was a pure power of 2, and it is extraordinarily nice.
Otherwise, $y$ contains an odd factor greater than 1, which means the number of odd divisors exceeds the number of even divisors, so $x$ is not extraordinarily nice.
Print "yes" if $x$ is extraordinarily nice, and "no" otherwise.

The algorithm works because powers of 2 have exactly one odd divisor, 1, and all other divisors are even, forming a one-to-one match with the power counts. If there is any odd factor greater than 1, the odd divisors outnumber the even divisors, breaking the condition. This invariant guarantees correctness.

Python Solution

import sys
input = sys.stdin.readline

x = int(input())
y = x

while y % 2 == 0:
    y //= 2

if y == 1:
    print("yes")
else:
    print("no")

We use y as a working copy to avoid modifying x. The while loop strips all powers of 2 from y. If y becomes 1, no odd factors remain, confirming $x$ is a power of 2. Using integer division // ensures that we stay in integer space, avoiding subtle floating-point errors.

Worked Examples

Example 1: x = 2

Step	y	y % 2 == 0?	Action
1	2	True	y //= 2 → y = 1
2	1	False	Exit loop

Check y == 1 → True → Output: "yes". This demonstrates that 2, which has divisors {1,2}, is extraordinarily nice.

Example 2: x = 6

Step	y	y % 2 == 0?	Action
1	6	True	y //= 2 → y = 3
2	3	False	Exit loop

Check y == 1 → False → Output: "no". 6 has divisors {1,2,3,6}; odd divisors {1,3} = 2, even divisors {2,6} = 2. Wait, it seems equal. But the divisors count: odd 2, even 2. Actually, this is "yes". Hmm, let's carefully consider:

Divisors of 6: {1,2,3,6}. Odd: {1,3} → 2. Even: {2,6} → 2. Number of evens = number of odds = 2.

Ah, this is an exception: numbers like 6 are not powers of 2 but still have equal even and odd divisors. So my previous claim about powers of 2 needs refinement.

Let's refine the observation:

Let $x = 2^a \cdot m$, $m$ odd.
Odd divisors come from odd numbers dividing $m$. Count: $\tau(m)$, the number of divisors of $m$.
Even divisors come from multiplying 2^k (k ≥ 1) with divisors of $m$. Count: a * τ(m)? Actually, it's more subtle.

Better approach: Count all divisors, split by parity. For small $x \le 1000$, brute-force counting is safe.

New optimal algorithm for safety: iterate i from 1 to sqrt(x), check if i divides x. Count odd and even divisors exactly. Return "yes" if counts equal. This avoids misclassification.

Python Solution (Brute-Force, Correct for all cases)

import sys
input = sys.stdin.readline

x = int(input())
odd = 0
even = 0

for i in range(1, x + 1):
    if x % i == 0:
        if i % 2 == 0:
            even += 1
        else:
            odd += 1

print("yes" if odd == even else "no")

We check all divisors explicitly. This avoids missing numbers like 6 where even and odd divisors balance but the number is not a power of 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(x)	Looping through 1..x to find divisors
Space	O(1)	Only two counters required

Given $x \le 1000$, this is well within the 2-second time limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    odd = 0
    even = 0
    x = int(input())
    for i in range(1, x + 1):
        if x % i == 0:
            if i % 2 == 0:
                even += 1
            else:
                odd += 1
    return "yes" if odd == even else "no"

# provided sample
assert run("2\n") == "yes", "sample 1"

# custom cases
assert run("1\n") == "no", "minimum input, only odd divisor"
assert run("6\n") == "yes", "balanced divisors"
assert run("8\n") == "no", "power of 2 > 2, odd divisors = 1, evens = 3"
assert run("9\n") == "no", "odd number, all divisors odd"