纪念一下,两件事。
$1.$ 打 $YACS$ 一年了,时间过得好快啊。
$2.$ 第一次 $AK$ 乙组。
高精板子。$8$ 进制转十进制,很简单。
小数部分第一位的数字乘上 $8^{-1}$,第二位就乘上 $8^{-2}$,以此类推。
加起来就是答案,可是用 $double$ 来算会爆精度,所以用高精。
这道题的重点是如何算 $8^{-i}$,这个数字给的很巧。
我们小学就学过,$8$ 的好朋友是 $125$,这两个数相乘得到的就是 $1000$
现在就要想办法凑 $125$ 出来。$8^{-i}$ 不是很好用高精计算,变成 $\frac{1}{8^i}$
但是一个数除以 $8^i$ 也很难用高精算。
想办法凑出 $10^i$,那么上下同乘 $125^i$ 就可以了。
得到 $\frac{125^i}{1000^i}$,退化成普通高精。
还有一个问题,这个 $125^i$ 加在小数点后第几位?
很简单,拿 $3\times i + 1 - $ 他的位数就行了。
剩下的就很简单了,上代码:
#include <cstring> #include <iostream> using namespace std; char s[510]; int a[1105], b[1105], ans[3005]; int main () { a[1100] = 1; scanf ("%s", s + 1); int len = strlen (s + 1); for (int i = 1; i <= len; i ++) { for (int j = 1100; j >= 1; j --) a[j] *= 125; for (int j = 1100; j >= 1; j --) { a[j - 1] += a[j] / 10; a[j] %= 10; } if (s[i] != '0') { int t = s[i] - 48, fir; for (int j = 1100; j >= 1; j --) b[j] = a[j] * t; for (int j = 1100; j >= 1; j --) { b[j - 1] += b[j] / 10; b[j] %= 10; if (b[j] != 0) fir = j; } int size = 1101 - fir; int na = 3 * i + 1 - size, nb = fir; while (nb != 1101) { ans[na] += b[nb]; na ++; nb ++; } for (int i = 3000; i >= 1; i --) { ans[i - 1] += ans[i] / 10; ans[i] %= 10; } } } int tmp = 0; for (int i = 3000; i >= 1; i --) if (ans[i] != 0 && !tmp) tmp = i; for (int i = 1; i <= tmp; i ++) cout << ans[i]; return 0; }
标签:fir,10,int,题解,乙组,--,125,ans,八进制 From: https://www.cnblogs.com/Xy-top/p/17045795.html