[P9532 [YsOI2023] 前缀和]

· · 题解

原题

分析&思路

观察题目给出的数列，可以发现除第一，二个数外，每个数都等于上一个数乘 2，因此，除了第一，二个数，每个数必须都是偶数。所以，我们可以根据 x 的奇偶性来分讨：

  1. $x$ 必定为第一或第二个数，要使结果最小 $x$ 需要是第一个数，而乘 $2$ 的次数为 $n - 2$ 次（除了第一，二个数），因此结果为 $x \times 2^{n - 2}$。
  2. 也可以根据如上方法先算出第一个数，再根据如上~~柿子~~式子计算出结果，得到第一个数只要让 $x$ 不断除以二直到除成奇数为止，原因如上，但同时也要满足当前遍历过的数字个数小于等于 $n$，用一个变量记录，注意初始值设成 $2$（$x$ 和前两个数中的一个，因为前两个数一样，一共是两个数）。

注意：不开 long long 见祖宗。

代码

#include <bits/stdc++.h>
using namespace std;
int t , n , x;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> x;
        long long ans;
        if (x % 2) ans = x * pow(2 , (n - 2));
        else
        {
            int tx = x , sum = 2;
            while (!(tx % 2) && sum < n) {tx /= 2; ++sum;}
            ans = tx * pow(2 , (n - 2));
        }
        cout << ans << endl;
    }
    return 0;
}