[已解决]求最大奇约数

柿子饼同学

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

样例:输入:

1. 6
   
2. 1 3
   
3. 1 4
   
4. 3 9
   
5. 14 67
   
6. 62 129
   
7. 75 168

复制代码

输出:

1. 5
   
2. 6
   
3. 29
   
4. 1468
   
5. 4320
   
6. 7576

复制代码

解释:

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

复制代码

题解:

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int t, a, b;
   
5. 
   
6. long long query(int x) { // 这个函数的算法是什么样的
   
7.     long long sum = 0;
   
8.     for (long long i = x; i; i >>= 1) {
   
9.         sum += ((i + 1) / 2) * ((i + 1) / 2);
   
10.     }
    
11.     return sum;
    
12. }
    
13. 
    
14. int main() {
    
15.     ios::sync_with_stdio(0);
    
16.     cin.tie(0);
    
17.     cout.tie(0);
    
18. 
    
19.     cin >> t;
    
20.     while (t--) {
    
21.         cin >> a >> b;
    
22.         cout << query(b) - query(a - 1) << endl;
    
23.     }
    
24. 
    
25.     return 0;
    
26. }

复制代码

解释 :
谢谢回答, 求教

最佳答案

月排行榜 / 总排行榜

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