13

我在一些在线论坛上看到了以下面试问题。对此有什么好的解决方案？

获取5^1234566789893943的最后1000位

4

8 回答 8

12

简单算法：

1. Maintain a 1000-digits array which will have the answer at the end
2. Implement a multiplication routine like you do in school. It is O(d^2).
3. Use modular exponentiation by squaring.

迭代取幂：

array ans;
int a = 5;

while (p > 0) {

    if (p&1) {

       ans = multiply(ans, a)
    }

    p = p>>1;

    ans = multiply(ans, ans);
}

multiply: multiplies two large number using the school method and return last 1000 digits.

时间复杂度： O(d^2*logp)，其中 d 是所需的最后一位数，p 是幂。

于 2014-07-18T04:46:46.410 回答
6

这个问题的一个典型解决方案是使用模运算和取幂，通过平方来计算5^1234566789893943除以 时的余数10^1000。但是，在您的情况下，这仍然不够好，因为它需要大约 1000*log(1234566789893943) 操作，这并不算多，但我将提出一种更通用的方法，该方法适用于更大的指数值。

您将不得不使用更复杂的数论。您可以使用欧拉定理更有效地获得5^1234566789893943模的其余部分。2^1000表示r。也很明显 可以5^1234566789893943被 整除5^1000。

之后，您需要找到一个数字 d 这样5^1000*d = r(modulo 2^1000)。要解决这个方程，你应该计算5^1000(modulo 2^1000)。之后剩下的就是做除法模2 ^ 1000。再次使用欧拉定理，这可以有效地完成。使用那个x^(phi(2^1000)-1)*x =1(modulo 2^1000). 这种方法速度更快，是唯一可行的解​​决方案。

于 2014-07-18T17:22:14.220 回答
2

我们需要知道的技术是通过平方和模求幂。我们还需要BigInteger在Java中使用。

Java中的简单代码：

BigInteger m = //BigInteger of 10^1000

BigInteger pow(BigInteger a, long b) {
   if (b == 0) {
      return BigInteger.ONE;
   }
   BigInteger val = pow(a, b/2);
   if (b % 2 == 0)
       return (val.multiply(val)).mod(m);
   else
       return (val.multiply(val).multiply(a)).mod(m);
}

在 Java 中，函数modPow为您完成了所有工作（感谢 Java）。

于 2014-07-18T04:18:46.330 回答
2

关键词是“模幂”。Python内置了：

Python 3.4.1 (v3.4.1:c0e311e010fc, May 18 2014, 10:38:22) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> help(pow)
Help on built-in function pow in module builtins:

pow(...)
    pow(x, y[, z]) -> number

    With two arguments, equivalent to x**y.  With three arguments,
    equivalent to (x**y) % z, but may be more efficient (e.g. for ints).

>>> digits = pow(5, 1234566789893943, 10**1000)
>>> len(str(digits))
1000
>>> digits
4750414775792952522204114184342722049638880929773624902773914715850189808476532716372371599198399541490535712666678457047950561228398126854813955228082149950029586996237166535637925022587538404245894713557782868186911348163750456080173694616157985752707395420982029720018418176528050046735160132510039430638924070731480858515227638960577060664844432475135181968277088315958312427313480771984874517274455070808286089278055166204573155093723933924226458522505574738359787477768274598805619392248788499020057331479403377350096157635924457653815121544961705226996087472416473967901157340721436252325091988301798899201640961322478421979046764449146045325215261829432737214561242087559734390139448919027470137649372264607375942527202021229200886927993079738795532281264345533044058574930108964976191133834748071751521214092905298139886778347051165211279789776682686753139533912795298973229094197221087871530034608077419911440782714084922725088980350599242632517985214513078773279630695469677448272705078125
>>>
于 2014-07-18T15:04:08.020 回答
1

使用同余并应用模运算。平方和乘法算法。如果您将任何以 10 为底的数字除以 10，则余数代表最后一位。即23422222=2342222*10+2

所以我们知道：

5=5(mod 10)
5^2=25=5(mod 10)  
5^4=(5^2)*(5^2)=5*5=5(mod 10)
5^8=(5^4)*(5^4)=5*5=5(mod 10)

...并继续前进，直到达到该指数

或者，您可以意识到，随着我们继续前进，您会不断获得 5 作为余数。

于 2014-07-18T03:48:53.460 回答
0

将数字转换为字符串。

在字符串上循环，从最后一个索引开始，直到 1000。

然后反转结果字符串。

于 2014-07-18T03:32:37.243 回答
0

我在这里根据一些提示发布了一个解决方案。

#include <vector>
#include <iostream>

using namespace std;

vector<char> multiplyArrays(const vector<char> &data1, const vector<char> &data2, int k) {
    int sz1 = data1.size();
    int sz2 = data2.size();
    vector<char> result(sz1+sz2,0);

    for(int i=sz1-1; i>=0; --i) {
        char carry = 0;
        
        for(int j=sz2-1; j>=0; --j) {
            char value = data1[i] * data2[j]+result[i+j+1]+carry;  
            
            carry = value/10;            
            result[i+j+1] = value % 10;
        }

        result[i]=carry;
    }
    if(sz1+sz2>k){
        vector<char> lastKElements(result.begin()+(sz1+sz2-k), result.end());
        return lastKElements;
    }
    else
        return result;
}

vector<char> calculate(unsigned long m, unsigned long n, int k) {
    if(n == 0) {
        return vector<char>(1, 1);
    } else if(n % 2) { // odd number
        vector<char> tmp(1, m);
        vector<char> result1 = calculate(m, n-1, k);
        return multiplyArrays(result1, tmp, k);
    } else {
        vector<char> result1 = calculate(m, n/2, k);
        return multiplyArrays(result1, result1, k);
    }
}

int main(int argc, char const *argv[]){


    vector<char> v=calculate(5,8,1000);
    for(auto c : v){
        cout<<static_cast<unsigned>(c);
    }

}
于 2014-07-18T18:24:11.150 回答
-2

我不知道 Windows 是否可以显示一个大数字（或者我的计算机是否足够快以显示它）但我想你可以使用这个代码和算法：

ulong x = 5; //There are a lot of libraries for other languages like C/C++ that support super big numbers. In this case I'm using C#'s default `Uint64` number.
for(ulong i=1; i<1234566789893943; i++)
{
    x = x * x; //I will make the multiplication raise power over here
}
string term = x.ToString(); //Store the number to  a string. I remember strings can store up to 1 billion characters.

char[] number = term.ToCharArray(); //Array of all the digits
int tmp=0;
while(number[tmp]!='.') //This will search for the period.
tmp++;

tmp++; //After finding the period, I will start storing 1000 digits from this index of the char array

string thousandDigits = ""; //Here I will store the digits.

for (int i = tmp; i <= 1000+tmp; i++)
{
    thousandDigits += number[i]; //Storing digits
}

以此为参考，我想如果您想尝试获取此数组的最后1000 个字符，请在上述代码的 for 中更改为：

string thousandDigits = "";

for (int i = 0; i > 1000; i++)
{
    thousandDigits += number[number.Length-i]; //Reverse array... ¿?
}

由于我不使用超级超级 looooong 数字，我不知道我的计算机是否可以得到这些，我尝试了代码并且它有效但是当我尝试在控制台中显示结果时它只是让指针闪烁 xD 猜猜它是还在工作。没有专业处理器。如果你想试试看：P

于 2014-07-18T03:56:27.477 回答