Hello everyone, I am Xiao C. “I heard that this year’s GESP_C++ Level 2 programming problems are quite challenging.” Today, I worked on the problems and found that the questions did not deviate from the syllabus, but the difficulty has increased. It tests students’ ability to interpret the questions, hoping that students can extract key information from the questions, while also assessing students’ problem-solvingcomprehensiveabilities which are no longer limited tosingleknowledge points. This ability requires long-term accumulation and sedimentation, and cannot be achieved overnight. It requires students to have a deep integrated understanding of logic, mathematics, and grammar, rather than simply memorizing “template code”.Let’s take a look at this problem:【Problem】: For a positive integer n, 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 integers l and r, please find out how many integers n satisfy l ≤ n ≤ r that are power sum numbers.【Input】: One line, containing two positive integers l and r, with the meanings as above.【Output】: Output one line, an integer representing the count of power sum numbers between l and r.【Sample Input】: 2 8【Sample Output】: 6Solution Approach:Let’s understand this statement: If an integer n can be expressed in the form2^x + 2^y, then the binary representation of this integer n has either 1 or 2 ones. Here are some specific examples:For instance, when n = 12, its binary representation is 1100, which is equivalent to 2^3 + 2^2, or 8 + 4 = 12. By observation, we find that it has 2 ones in its binary representation, which conforms to“If an integer n can be expressed in the form2^x + 2^y, then the binary representation of this integer n has either 1 or 2 ones“Now consider when n = 16, its binary representation is 10000, which is equivalent to 2^4, or 8 + 8 = 16. By observation, we find that it has 1 one in its binary representation,which conforms to“If an integer n can be expressed in the form2^x + 2^y, then the binary representation of this integer n has either 1 or 2 ones“You can take any example and find that the binary representation of n (n>1) has only 1 or 2 ones.Therefore, the first solution approach for this problem is: perform binary decomposition on n (n>1), and when n=1, it can be excluded because n=1 cannot be expressed as2^x + 2^y.
#include<bits/stdc++.h>using namespace std;
int l, r, ans;int count(int x) {int t = 0;// Count how many remainders are 1, which corresponds to how many binary bits are 1while(x) { t += x % 2; x /= 2;}
return t;}
int main(){scanf("%d%d", &l, &r);// When a certain number is 1, it cannot be expressed as 2^x+2^yif (l == 1) l++;
for(int i=l; i<=r; i++) {if(count(i)<=2) ans++;}
printf("%d\n",ans);return 0;}The above is the first solution approach, which may be difficult for students to think of. The easiest approach is to solve it directly using brute force. That is, we can directly enumerate t1=2^a, and then enumerate t2=2^b, and see which combinations of t1+t2 can form values, as shown in the reference code below:
#include<bits/stdc++.h>using namespace std;
int main(){ int l, r, t1, t2, n, cnt = 0; cin >> l >> r; t1 = 1;while(t1 <= r) { t2 = t1;while(t2 <= r) { n = t1 + t2;if(n >= l && n <= r) cnt++; t2*=2; } t1 *= 2; } cout << cnt << endl;return 0;}In the beginning of my teaching, I always focused on teaching students grammar, but later I gradually realized that I should teach problem-solving thinking and methods. I realized this a bit late, but fortunately, I stopped the loss in time. In the future, I must urge myself to do more thinking problems and learn more methods. Goodbye!