[已解决]求最大奇约数

柿子饼同学

题目在下 , 主要 query() 函数看不懂, 知道充当的是差不多前缀和的一个东西, 但是不知道为什么这么算(别走, 有题解代码在下面)

样例:输入:

6
1 3
1 4
3 9
14 67
62 129
75 168

输出:

5
6
29
1468
4320
7576

解释:

前3个询问:
1+1+3=5
1+1+3+1=6
3+1+5+3+7+1+9=29

题解:

#include <bits/stdc++.h>
using namespace std;

int t, a, b;

long long query(int x) { // 这个函数的算法是什么样的
    long long sum = 0;
    for (long long i = x; i; i >>= 1) {
        sum += ((i + 1) / 2) * ((i + 1) / 2);
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--) {
        cin >> a >> b;
        cout << query(b) - query(a - 1) << endl;
    }

    return 0;
}

解释 :
谢谢回答, 求教

最佳答案

月排行榜 / 总排行榜

jhq999

2022-7-26 11:44:48

我理解
奇数最大的奇约数是它自己
偶数每次除以2（也就是右移1）；直到不能被2整除的就是最大奇约数
至于
连续区间
1~10 奇数最大奇约数和是（1+9）*5/2   等差数列求和（1+n)*n/2
剩下偶数是
2 4 6 8 10
/2
得到1 2 3 4 5 奇数最大奇约数和是（1+3）*3/2
2 4
/2
1 2        1
2
/2
1

跳转到最佳答案楼层

柿子饼同学

jhq999

我理解
奇数最大的奇约数是它自己
偶数每次除以2（也就是右移1）；直到不能被2整除的就是最大奇约数
至于
连续区间
1~10 奇数最大奇约数和是（1+9）*5/2   等差数列求和（1+n)*n/2
剩下偶数是
2 4 6 8 10
/2
得到1 2 3 4 5 奇数最大奇约数和是（1+3）*3/2
2 4
/2
1 2        1
2
/2
1