题解：CF1968C Assembly via Remainders

· · 题解

题意简述

给定长度为 n-1 的数列 x_i，构造长度为 n 的数列 a_i，满足 x_i=a_i \bmod a_{i-1}。

解题思路

令：

a_i=a_{i-1}+x_i

则：

\begin{aligned} x_i &= a_i \bmod a_{i-1} \\ &= (a_{i-1}+x_i) \bmod a_{i-1} \\ &= a_{i-1} \bmod a_{i-1} + x_i \bmod a_{i-1} \\ &= x_i \bmod a_{i-1} \end{aligned}

不难发现，当 a_{i-1} 较大时即可满足条件。

由于 x_i \le 500，a_i \le 10^9，所以不妨令 a_1 为一个较大的数。

参考代码

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

const int N=200005;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        a[1]=100526;
        for(int i=2;i<=n;i++)
        {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}