【题解】洛谷 P9532 [YsOI2023] 前缀和

原题链接

【LGR-151-Div.2】洛谷 8 月月赛 II & YsOI2023 T1

解题思路

设有一序列 a，其中 a₁ = a₂，第 k( ≥ 3) 项为前 k-1 项的前缀和。可以发现前 q 项分别为第一项的 2⁰ 倍，2⁰ 倍，2¹ 倍，2² 倍，2³ 倍…2^q-3 倍，2^q-2 倍。

扩展到整个序列中，可得第 i( ≥ 3) 项一定为 2^i-2a₁。要保证 a_n 尽量小，就可以让 x 出现的位置尽量靠后。

那么可以让 i 从 n-2 开始枚举，每次减1。如果 x 能被 2ⁱ 整除，说明 x 最后也只能是序列中第 i+2 个数（前面多减了一个2）；再从 i+3 开始循环到 n，依次乘2，乘到 n 次就是 a_n 的最小值了。当然，如果 n = 2，则直接输出 x 就好啦。

注意：乘起来的结果可能会很大，要开 long long。

代码实现

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T;
 4 int main() {
 5     for (cin >> T; T --;){
 6         int n;
 7         long long x;
 8         cin >> n >> x;
 9         if (n == 2){
10             cout << x << endl;
11             continue;
12         }
13         for (int i = n - 2; ; i --)
14             if (!(x % (1 << i))){
15                 for (int j = i + 3; j <= n; j ++)
16                     x <<= 1; // 左移1，相当于乘2
17                 cout << x << endl;
18                 break;
19             }
20     }
21     return 0;
22 }