#P17849. [Ontak2019]FIB
[Ontak2019]FIB
— 斐波那契进制除法
定义斐波那契数列:
$$F_0=1,\qquad F_1=2,\qquad F_i=F_{i-1}+F_{i-2}\quad(i\ge2).$$每个非负整数 都有唯一的标准斐波那契进制表示 ,满足:
- ;
- 每位为0或1,非零数的最高位 ;
- 不存在两个相邻的1。
整数0的表示长度为0。注意输入和输出均按低位在前、高位在后的顺序给出各位。
给定一个正整数 的标准斐波那契进制表示,以及 ,求 的标准斐波那契进制表示。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例占两行:第一行先给出位数 ,然后是 个整数 ;第二行给出除数 。
输出格式
每个测试用例输出一行:先输出答案的位数 ,再输出 个二进制位,仍按低位在前的顺序。
若商为0,只输出一个整数 0,不要输出 1 0。
数据范围
,,。所有用例的 之和不超过20000000。保证输入表示合法且表示正整数。英文版漏写了 的上限,这里按同一 PDF 中的波兰文版本补全。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | 30 | |
| 3 | ||
| 4 |
样例 1
输入:
2
7 0 1 0 0 1 0 1
2
1 1
3
输出:
6 0 1 0 0 0 1
0