C++ Practice [GESP2506 Level 2] Power Sum Numbers

GESP Level 2 practice, loops and enumeration, difficulty beginner.

• CCF-GESP C++ Assessment Standards

  Hong Yang, WeChat Official Account: Hong Yang’s Programming Class CCF-GESP C++ Assessment Standards

Comprehensive Guide – [GESP2506 Level 2] Power Sum Numbers

Problem Requirements

Problem Description

For a positive integern, if n can be expressed as the sum of two powers of 2, i.e., n = 2^x + 2^y (where x and y are non-negative integers), then n is called a power sum number.Given positive integersl and r, please find out how many integers n satisfy l ≤ n ≤ r that are power sum numbers.

Input Format

One line, containing two positive integersl and r, as described above.

Output Format

Output one line, an integer representingthe count of power sum numbers between l and r.

Input and Output Examples

Input #1

2 8

Output #1

6

Input #2

10 100

Output #2

20

Data Range

 For all test cases, ensure 1 ≤ l ≤ r ≤ 1e4.

Problem Analysis

Solution Approach

Core Idea: Enumerate all possible combinations of powers of 2 and check if their sum falls within the given range [l, r].

Specific Steps:

1. Outer loop enumerates the first power of 2 x (1, 2, 4, 8, 16, …)

2. Inner loop enumerates the second power of 2 y (starting from x to avoid double counting)

3. For each pair (x, y), calculate x+y

4. If x+y is within the range [l, r], increment the counter by 1

Key Points:

• The inner loop starts from y=x to avoid double counting (e.g., 2+4 and 4+2 are considered the same)

• Efficiently generate the sequence of powers of 2 using x*=2 and y*=2

• The loop automatically terminates when x > r, since x+y ≥ x > r

Complexity Analysis:

• Time complexity is O(log²r)

• Space complexity is O(1)

Example Code

#include <bits/stdc++.h>using namespace std;int main(){    int l, r, ans = 0;    scanf("%d%d", &l, &r);  // Input the left and right endpoints of the interval        // Outer loop: enumerate the first power of 2 x    for(int x = 1; x <= r; x *= 2) {        // Inner loop: enumerate the second power of 2 y (starting from x to avoid duplicates)        for(int y = x; y <= r; y *= 2) {            // Check if x+y is within the interval [l, r]            if(x + y >= l && x + y <= r) {                ans++;  // If it is a power sum number, increment the counter            }        }    }        printf("%d\n", ans);  // Output the result    return 0;}

“Comprehensive Guide–” series problems can be evaluated online atInformatics Olympiad Comprehensive Guide (C++ Version).