在a，b，k爲非常大的整數（小於10e18）的小數點a/b的小數點後面找到第k個數字

Question

我的任務是在小數點後面找到第k個位置的數字（ A/b）。 昨天我發現了這個算法。
爲了得到小數點後的任何數字，我產生一個叫做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循環終止後，數組將存儲重複內的每個數字。根據陣列中的位數，我們可以計算第k位。
  然而，該算法仍然被證明是耗時的，因爲在a和b是兩個連續整數的情況下，重複變得非常大。 你能幫我一下嗎？

Answer 1

你的循環計算結果是10 *（a * 10 ^k％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。