对于正整数 n,如果 n 可以表为两个 2 的次幂之和,即 n = 2x + 2y(x, y 均为非负整数),那么称 n 为幂和数。
给定正整数 l, r,请你求出满足 l ≤ n ≤ r 的整数 n 中有多少个幂和数。
对于正整数 n,如果 n 可以表为两个 2 的次幂之和,即 n = 2^x + 2^y(x, y 均为非负整数),那么称 n 为幂和数。
给定正整数 l, r,请你求出满足 l ≤ n ≤ r 的整数 n 中有多少个幂和数。
请参考题目描述中的样例
判断 n 能否表示为 2^x + 2^y。枚举 x 和 y,计算 2^x + 2^y 是否等于 n。
读入正整数。
从 0 到 30 枚举。
2^x + 2^y == n 则找到。
点"算一下"按钮开始 →
读入正整数。
从 0 到 30 枚举。
2^x + 2^y == n 则找到。
#include <iostream> using namespace std; int main() { int n; cin >> n; bool found = false; for (int x = 0; x <= 30 && !found; x++) for (int y = x; y <= 30; y++) if ((1<<x) + (1<<y) == n) { found = true; break; } cout << (found ? "Yes" : "No") << endl; return 0; }
时间:根据算法结构分析时间复杂度。
空间:只使用少量变量,O(1)。
✅ 在数据范围内轻松通过!
// 嵌套循环遍历矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 处理 (i, j) } } // 取余判断整除 if (n % k == 0) { ... } // 数位分离 while (n > 0) { d = n % 10; n /= 10; }