jjzjj

c++ - 找出分数 a/b 的小数点后第 k 位，其中 a,b,k 是非常大的整数(小于 10e18)

coder 2024-02-22 原文

我的任务是找到分数 (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/

数点ampuintsection64c++algorithmmath

有关c++ - 找出分数 a/b 的小数点后第 k 位，其中 a,b,k 是非常大的整数(小于 10e18)的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  5. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  6. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

  7. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  8. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  9. ruby-on-rails - 如何找出拦截 'method_missing' 的内容 - 2

    使用Ruby1.8.6/Rails2.3.2我注意到在我的任何ActiveRecord模型类上调用的任何方法都返回nil而不是NoMethodError。除了烦人之外，这还破坏了动态查找器(find_by_name、find_by_id等)，因为即使存在记录，它们也总是返回nil。不从ActiveRecord::Base派生的标准类不受影响。有没有办法追踪在ActiveRecord::Base之前拦截method_missing的是什么？更新:切换到1.8.7后，我发现(感谢@MichaelKohl)will_paginate插件首先处理method_missing。但是will_pa

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐