To solve this problem, we need to find the number of pairs of integers (a, b) such that (1 \leq a \leq b \leq n) and the sum (a + b) is a power of 2.

Approach

1. Identify Valid Powers of 2: The sum (a + b) must be a power of 2. The possible values of this sum range from 2 (since (a) and (b) are at least 1) up to (2n) (since both (a) and (b) are at most (n)).
2. Count Valid Pairs for Each Power: For each valid power of 2 (let's denote it as (s)):
   • Lower Bound: The minimum value of (a) is the maximum of 1 and (s - n) (since (b = s - a) must be ≤ (n)).
   • Upper Bound: The maximum value of (a) is the minimum of (s//2) (since (a ≤ b)) and (n) (since (a ≤ n)).
   • Valid Pairs: If the upper bound is greater than or equal to the lower bound, the number of valid pairs is (upper - lower + 1).

Solution Code

n = int(input())
total = 0
s = 2  # Start with the smallest power of 2 (sum of 1+1)
while s <= 2 * n:
    lower = max(1, s - n)
    upper = min(s // 2, n)
    if upper >= lower:
        total += upper - lower + 1
    s *= 2  # Next power of 2
print(total)

Explanation

• Powers of 2: We generate all powers of 2 up to (2n) because any sum larger than (2n) would require at least one of (a) or (b) to be greater than (n).
• Bounds Calculation: For each power (s), we calculate the valid range of (a) values. The lower bound ensures (b = s - a) is ≤ (n), and the upper bound ensures (a ≤ b) and (a ≤ n).
• Efficiency: The number of powers of 2 up to (2n) is logarithmic (e.g., for (n = 100000), there are about 18 powers), so the solution is very efficient.

This approach efficiently counts all valid pairs with a time complexity of (O(\log(2n))), which is optimal for the given problem constraints.

Answer: The code will output the number of valid pairs for the given (n). For example, if (n = 2), the output is 2. If (n = 3), the output is 4. If (n = 1), the output is 1. Etc.

(\boxed{2}) (for (n = 2) as an example)

作者声明:本文包含人工智能生成内容。