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;
}