【AcWing寒假每日一题2023】Day14——如此编码
目录
- 问题描述
- 思路与代码
问题描述
原题链接🔗：4699. 如此编码
思路与代码
本题看似很长，但分析起来很简单。
根据题意，有
m = c 0 b 1 + c 1 b 2 + ⋯ + c n − 1 b n = b 1 + a 1 b 2 + a 1 a 2 b 3 + ⋯ + a 1 a 2 ⋯ a n − 1 b n = b 1 + a 1 ( b 2 + a 2 b 3 + ⋯ + a 2 ⋯ a n − 1 b n ) \begin{aligned} m&=c_0b_1+c_1b_2+\cdots+c_{n-1}b_n \\ &=b_1+a_1b_2+a_1a_2b_3+\cdots+a_1a_2\cdots a_{n-1}b_n \\ &=b_1+a_1(b_2+a_2b_3+\cdots+a_2\cdots a_{n-1}b_n) \end{aligned} m=c0b1+c1b2+⋯+cn−1bn=b1+a1b2+a1a2b3+⋯+a1a2⋯an−1bn=b1+a1(b2+a2b3+⋯+a2⋯an−1bn)
因 0 ≤ b 1 < a 1 0\leq b_1<a_1 0≤b1<a1，故 m mod a 1 = b 1 mod a 1 = b 1 m\;\text{mod}\;a_1=b_1\;\text{mod}\;a_1=b_1 mmoda1=b1moda1=b1。再令 m = m / a 1 m = m/a_1 m=m/a1，有
m = b 2 + a 2 b 3 + a 2 a 3 b 4 + ⋯ + a 2 ⋯ a n − 1 b n m=b_2+a_2b_3+a_2a_3b_4+\cdots+a_2\cdots a_{n-1}b_n m=b2+a2b3+a2a3b4+⋯+a2⋯an−1bn
以此类推即可求出 b 2 , ⋯ , b n b_2,\cdots,b_n b2,⋯,bn。
AC代码：
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
while (n--) {
int a;
cin >> a;
cout << m % a << " ";
m /= a;
}
return 0;
}