AT_past202107_g べき表現题解-深圳市維司達科技有限公司

AT_past202107_g べき表現

Link: https://atcoder.jp/contests/past202107-open/tasks/past202107_g

题目描述

给定一个整数n ( 1 ≤ n ≤ 10 15 ) n(1\le n\le 10^{15})n(1≤n≤1015)，请输出一个长为m ( 1 ≤ m ≤ 100 ) m(1\le m\le 100)m(1≤m≤100)的整数数列a aa，满足：

∑ a i = n \sum a_i=n∑ai=n；
∣ a i ∣ ≤ 10 18 |a_i|\le 10^{18}∣ai∣≤1018，且当i ≠ j i\neq ji=j时，∣ a i ∣ ≠ ∣ a j ∣ |a_i|\neq|a_j|∣ai∣=∣aj∣；
对于每一个满足1 ≤ i ≤ m 1\le i\le m1≤i≤m的整数i ii，∣ a i ∣ = 3 x |a_i|=3^x∣ai∣=3x，其中x xx为自然数。

数据保证，在本题数据范围下，数列a aa一定存在。若有多解，输出任一解即可。

输入格式

一行一个整数n nn。

输出格式

两行，第一行输出整数m mm，第二行输出m mm个整数，表示数列a aa。

输入输出样例 #1

输入 #1

输出 #1

2 9 -3

输入输出样例 #2

输入 #2

输出 #2

9 2187 27 1 -243 3 9 -81 6561 729

输入输出样例 #3

输入 #3

10120190919012

输出 #3

16 -1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609

Solution

本题可以视为平衡三进制的模版题。

1. 前置知识 - 平衡三进制

平衡三进制是一种以3 33为基数，以− 1 , 0 , 1 -1,0,1−1,0,1为基本数码的三进制计数体系。为便于书写，一般会将平衡三进制某一位上的− 1 -1−1用字母Z \text ZZ来表示。将一个平衡三进制数转化为十进制，只需要将对应数位上的数乘以3 33的幂次累加即可，计算方法和常规三进制的计算方法相同。

例如要将平衡三进制下的数字1 Z 101 1\text Z1011Z101转化为十进制，计算方法为：

( 1 Z 101 ) balance3 = 1 × 3 4 + ( − 1 ) × 3 3 + 1 × 3 2 + 0 × 3 1 + 1 × 3 0 = 64 (1\text Z101)_{\text{balance3}}=1\times3^4+(-1)\times3^3+1\times3^2+0\times3^1+1\times3^0=64(1Z101)balance3=1×34+(−1)×33+1×32+0×31+1×30=64

从上面的计算流程中我们很容易看出，对于一个给定的十进制数字n nn，只需要将其转化为平衡三进制，根据这个由− 1 , 0 , 1 -1,0,1−1,0,1构成的序列，就可以将其拆分为满足题意的正负3 33的幂次的组合。

由于平衡三进制不同于常规的三进制，其涉及到负数的数位，因此直接将十进制转化为平衡三进制可能有些困难，为此我们可以先将十进制转化为常规三进制，再转化为平衡三进制。

2. 十进制转化为常规三进制

十进制转化为普通三进制，只需要重复“模3 33然后整除3 33”的流程, 将给定的整数转化为一串由数字0 , 1 , 2 0,1,20,1,2构成的序列即可，参考代码如下：

inttp[100];voiddec2base3(longlongt)//将十进制转化为普通三进制, 使用数组存储每一位, 下标小的表示低位, 下标大的表示高位{intindex=0;//当前的数位while(t){tp[index]=t%3;t/=3;index+=1;}return;}

3. 常规三进制转化为平衡三进制

由于3 − 1 = 2 3-1=23−1=2，因此将常规三进制转化为平衡三进制时，需要将三进制上为2 22的位变成− 1 -1−1，然后进位。如果这个进位导致前一位变成3 33，也需要进位，以此类推，参考代码如下：

voidbase2balance3()//将普通三进制转化为平衡三进制, 平衡三进制的每一位由-1, 0或1构成{for(inti=0;i<=99;i+=1){if(tp[i]==2)//如果某一位是2, 这一位就变成-1, 然后高位增加1{tp[i]=-1;tp[i+1]+=1;}if(tp[i]==3)//如果某一位是3, 和普通三进制一样, 要进位{tp[i]=0;tp[i+1]+=1;}}}

4. 输出

按照平衡三进制的序列，输出1 11或− 1 -1−1乘以3 33的幂次即可。需要注意的是如果平衡三进制的某一位为0 00，答案中不能输出0 00，直接跳过。由于输出的第一行是个数，因此需要统计平衡三进制中不为零的数位个数。

参考代码：

for(index=99;index>=0;index-=1)if(tp[index])break;//找到第一个不为零的数位for(inti=index;i>=0;i-=1)if(tp[i])tot+=1;/*平衡三进制如果某一位是0, 就不输出, 所以要判断总共要输出多少位!*/printf("%d\n",tot);for(inti=index;i>=0;i-=1)if(tp[i])printf("%.0Lf ",powl(3.L,i)*tp[i]);

5. 完整代码

#pragmawarning(disable:4996)#include<cstdio>#include<algorithm>#include<cmath>longlongn,index,tot=0;inttp[100];voiddec2base3(longlongt)//将十进制转化为普通三进制, 使用数组存储每一位, 下标小的表示低位, 下标大的表示高位{intindex=0;//当前的数位while(t){tp[index]=t%3;t/=3;index+=1;}return;}voidbase2balance3()//将普通三进制转化为平衡三进制, 平衡三进制的每一位由-1, 0或1构成{for(inti=0;i<=99;i+=1){if(tp[i]==2)//如果某一位是2, 这一位就变成-1, 然后高位增加1{tp[i]=-1;tp[i+1]+=1;}if(tp[i]==3)//如果某一位是3, 和普通三进制一样, 要进位{tp[i]=0;tp[i+1]+=1;}}}intmain(){scanf("%lld",&n);dec2base3(n);base2balance3();/*调试用代码块 - 一般用Z表示-1, 倒序输出即可得到输入整数的平衡三进制的序列 for (int i = 99; i >= 0; i -= 1) { if (tp[i] == 0) putchar('0'); if (tp[i] == -1) putchar('Z'); if (tp[i] == 1) putchar('1'); } */for(index=99;index>=0;index-=1)if(tp[index])break;for(inti=index;i>=0;i-=1)if(tp[i])tot+=1;/*平衡三进制如果某一位是0, 就不输出, 所以要判断总共要输出多少位!*/printf("%d\n",tot);for(inti=index;i>=0;i-=1)if(tp[i])printf("%.0Lf ",powl(3.L,i)*tp[i]);}