问题描述:

I saw the following interview question on some online forum. What is a good solution for this?

Get the last 1000 digits of 5^1234566789893943

**Simple algorithm:**

```
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.
```

**Iterative exponentiation:**

```
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.
```

**Time complexity:** **O(d^2*logp)** where d is number of last digits needed and p is power.

A typical solution for this problem would be to use modular arithmetic and exponentiation by squaring to compute the remainder of `5^1234566789893943`

when divided by `10^1000`

. However in your case this will still not be good enough as it would take about 1000*log(1234566789893943) operations and this is not too much, but I will propose a more general approach that would work for greater values of the exponent.

You will have to use a bit more complicated number theory. You can use Euler's theorem to get the remainder of `5^1234566789893943`

modulo `2^1000`

a lot more efficiently. Denote that `r`

. It is also obvious that `5^1234566789893943`

is divisible by `5^1000`

.

After that you need to find a number d such that `5^1000*d = r(modulo 2^1000)`

. To solve this equation you should compute `5^1000(modulo 2^1000)`

. After that all that is left is to do division modulo 2^1000. Using again Euler's theorem this can be done efficiently. Use that `x^(phi(2^1000)-1)*x =1(modulo 2^1000)`

. This approach is way faster and is the only feasible solution.

The key phrase is "modular exponentiation". Python has that built in:

```
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
>>>
```

The technique we need to know is exponentiation by squaring and modulus. We also need to use BigInteger in Java.

Simple code in 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);
}
```

In Java, the function modPow has done it all for you (thank Java).

Use congruences and apply modular arithmetic. Square and multiply algorithm. If you divide any number in base 10 by 10 then the remainder represents the last digit. i.e. 23422222=2342222*10+2

So we know:
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)

....and keep going until you get to that exponent

OR, you can realize that as we keep going you keep getting 5 as your remainder.

I posted a solution based on some hints here.

```
#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);
}
}
```

Convert the number to a string.

Loop on the string, starting at the last index up to 1000.

Then reverse the result string.

I don't know if Windows can show a big number (Or if my computer is fast enough to show it) But I guess you *COULD* use this code like and algorithm:

```
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
}
```

Using this as a reference, I guess if you want to try getting the *LAST* 1000 characters of this array, change to this in the for of the above code:

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

As I don't work with super super looooong numbers, I don't know if my computer can get those, I tried the code and it works but when I try to show the result in console it just leave the pointer flickering xD Guess it's still working. Don't have a pro Processor. Try it if you want :P