跳到主要内容

偶数分解

题目描述​

米小游非常喜欢偶数，尤其是能被2整除很多次的偶数。对于一个偶数n，米小游定义其"喜好值"为n能被2整除的次数。

例如，对于数字8，可以被2整除3次（8/2=4，4/2=2，2/2=1），所以喜好值为3。

现在，给定一个区间[l, r]，请你找出区间内所有偶数的最大喜好值和所有偶数的喜好值总和。

输入描述​

一行两个整数l和r，表示区间的左右边界（1 ≤ l ≤ r ≤ 10^5）。

输出描述​

输出两个整数，分别表示区间内偶数的最大喜好值和所有偶数的喜好值总和，用空格分隔。

示例​

输入：
1 10

输出：
3 8

解释：
区间[1,10]中的偶数有：2（喜好值1），4（喜好值2），6（喜好值1），8（喜好值3），10（喜好值1）
最大喜好值为3，喜好值总和为1+2+1+3+1=8。

解题思路​

遍历

  1. 遍历区间[l, r]中的所有整数
  2. 对于每个偶数，计算它的"喜好值"，即能被2整除的次数：
    • 使用辅助函数getLikeValue来计算单个数字的喜好值
    • 在函数中使用while循环，只要当前数字能被2整除，就将计数器加1，并将数字除以2
    • 当数字变为奇数时，循环结束，此时计数器的值就是该数字的喜好值
  3. 在遍历过程中直接维护最大喜好值和总喜好值，避免额外存储
  4. 输出最大喜好值和喜好值总和

时间复杂度: O(n*log(max_value))，其中n = r-l+1 空间复杂度: O(1)

C++ 解法​

#include <algorithm>
#include <iostream>

// 计算单个数的喜好值（能被2整除的次数）
int getLikeValue(int num) {
    int count = 0;
    while (num % 2 == 0) {
        count++;
        num /= 2;
    }
    return count;
}

int main() {
    int l, r;
    std::cin >> l >> r;

    int maxLike = 0;
    long long totalLike = 0;

    // 遍历区间内的每个数字
    for (int i = l; i <= r; i++) {
        if (i % 2 == 0) { // 只处理偶数
            int likeValue = getLikeValue(i);
            maxLike = std::max(maxLike, likeValue);
            totalLike += likeValue;
        }
    }

    std::cout << maxLike << " " << totalLike << endl;

    return 0;
}