我的任务是找到分数 (a/b) 小数点后第 k 位的数字。
昨天我发现了这个算法。
为了获得小数点后的任何数字,我生成了一个名为 rem 的变量并进行了循环
for (int i = 1; i <= k+1; i++)
{
rem = a%b;
a = rem*10;
}
cout << a/b;
循环将返回一个值,该值是小数点后的第 k 位。
但是这个任务要求我用a,b,k计算非常大的数(小于或等于10e18),所以代码肯定会超过时间限制。
- 找出重复前的数字个数。它是分母中因数 2 和 5 中较大的一个。
- 如果k不超过位数,运行for循环。
- 否则,我们仍然会运行 for 循环到 k+1。将除法的余数存储在变量 x 中。
- 用上面相同的内容运行一个 while 循环,直到余数再次具有 x 的值。此后,将除法的每一个商存储到一个名为qut的数组中。
- while 循环终止后,数组将存储 repetend 中的每个数字。根据数组中的位数,我们可以计算出第k位。
然而,这个算法仍然被证明是耗时的,因为在a和b是两个连续整数的情况下,repetend变得非常大。 你能帮我出主意吗?
最佳答案
您的 for 循环计算的实际上是 10 * (a*10k % b)/b。我们可以通过平方求幂来更有效地做到这一点。不过,我们必须小心不要在每一点溢出:
int kth_digit_frac(uint64_t a, uint64_t b, uint64_t k) {
return 10 * mulmodu64(a, powmod(10, k, b), b) / b;
}
// a*b % m, overflow safe
inline uint64_t mulmodu64(uint64_t a, uint64_t b, uint64_t m) {
#if defined(__GNUC__) && defined(__x86_64__)
uint64_t q, r;
asm("mulq %3;"
"divq %4;"
: "=a"(q), "=d"(r)
: "a"(a), "d"(b), "rm"(m)
: "cc");
return r;
#else
a %= m;
b %= m;
// No overflow possible.
if (a == 0) return 0;
if (b <= std::numeric_limits<uint64_t>::max() / a) return (a*b) % m;
uint64_t res = 0;
while (a != 0) {
if (a & 1) {
if (b >= m - res) res -= m;
res += b;
}
a >>= 1;
if (b >= m - b) b += b - m;
else b += b;
}
return res;
#endif
}
// b^e % m, overflow safe
inline uint64_t powmod(uint64_t b, uint64_t e, uint64_t m) {
uint64_t r = 1;
b %= m;
while (e) {
if (e % 2 == 1) r = mulmodu64(r, b, m);
b = mulmodu64(b, b, m);
e >>= 1;
}
return r;
}
对于适合 64 位整数的任何 a,b,k
,它会在眨眼间运行。
关于c++ - 找出分数 a/b 的小数点后第 k 位,其中 a,b,k 是非常大的整数(小于 10e18),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39612084/