AcWing4699 如此编码 题解

题目链接：AcWing4699 如此编码

题意：

给定长度为 $n$ 的数组 $a_i$ 和 $m$ ，求 $b_i$ ，其中 $m$ 的定义如下：

记 $c_i = \prod_{j = 1}^{i}a_i$ ，定义 $c_0=1$ ，则 $m = \sum_{i = 1}^{n} c_{i-1}\times b_i$

输入格式：

第一行给出 $n,m$ ，第二行给出 $a_i$ 。

输出格式：

一行，$n$ 个数，表示 $b_i$ 。

数据范围：

$1\le n\le 20,~a_i\ge 2,~0\le b_i\le a_i,~ c_n \le 10^9$

把 $m$ 的定义式展开

$$\textstyle m = b_1 + b_2a_1 + b_3a_1a_2 + \cdots + b_n\times\prod_{i=1}^{n}a_i$$

可以发现，当所有 $a_i$ 相等时，这就是一个 $a_i$ 进制的数。

因此我们从进制的角度出发。因为 $b_i < a_i$ ，所以我们可以直接用 $m \bmod a_1$ 求出 $b_1$

同理， $b_2 = \left\lfloor\frac{m}{a_1}\right\rfloor \bmod a_2$ 。那么我们只要循环就能求出 $b_2$ 了。

时间复杂度 $\mathcal{O}(n)$

代码：（有点过于短了）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(25))

int n,m,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; m /= a[i++])
        cout << m % a[i] << " \n"[i == n]; 
    return 0;
}