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 に答える
0

数値を文字列に変換します。

最後のインデックスから 1000 まで、文字列をループします。

次に、結果の文字列を逆にします。

于 2014-07-18T03:32:37.243 に答える
-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... ¿?
}

私は超超巨大な数字を扱っていないので、私のコンピューターがそれらを取得できるかどうかわかりません。コードを試してみましたが、コンソールに結果を表示しようとすると、ポインタがちらつくだけですxD推測まだ働いている。プロプロセッサを持っていません。必要に応じて試してみてください:P

于 2014-07-18T03:56:27.477 に答える