Я видел следующий вопрос интервью на каком-то онлайн-форуме. Какое для этого хорошее решение?
Получить последние 1000 цифр из 5 ^ 1234566789893943
Я видел следующий вопрос интервью на каком-то онлайн-форуме. Какое для этого хорошее решение?
Получить последние 1000 цифр из 5 ^ 1234566789893943
Простой алгоритм:
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 - степень.
Типичным решением этой проблемы было бы использование модульной арифметики и возведения в степень путем возведения в квадрат для вычисления остатка от 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)
. Этот подход намного быстрее и является единственно возможным решением.
Ключевая фраза - «модульное возведение в степень». В 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
>>>
Нам необходимо знать метод возведения в степень квадратом и модулем. Нам также нужно использовать 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).
Используйте сравнение и применяйте модульную арифметику. Алгоритм возведения в квадрат и умножения. Если вы разделите любое число с основанием 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 в качестве остатка.
Преобразуйте число в строку.
Цикл по строке, начиная с последнего индекса до 1000.
Затем переверните строку результата.
double
или 32-битный float
? Я так сбит с толку, но 64 бита немного ближе к 3000 бит, чем 32 бита, я думаю ...
- person holex; 18.07.2014
Я разместил здесь решение, основанное на некоторых подсказках.
#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);
}
}
Я не знаю, может ли 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
}
Используя это как ссылку, я думаю, если вы хотите попытаться получить LAST 1000 символов этого массива, измените это в for из приведенного выше кода:
string thousandDigits = "";
for (int i = 0; i > 1000; i++)
{
thousandDigits += number[number.Length-i]; //Reverse array... ¿?
}
Поскольку я не работаю с числами super super looooong, я не знаю, сможет ли мой компьютер их получить, я попробовал код, и он работает, но когда я пытаюсь показать результат в консоли, он просто оставляет указатель мерцания xD Угадайте, что это еще работает. Нет профессионального процессора. Попробуйте, если хотите: P
x=modpow(5,1234566789893943,10^1000)
и принять во внимание результат~3322 bit
long (log10 (10 ^ 1000) / log10 (2) = 1000 / 0.30103), поэтому используйте bigint или строковые числа с большими достаточно бит / цифр, чтобы избежать переполнения во время вычислений - person Spektre   schedule 18.07.2014