Хранение части большого числа

Question

Хранение части большого числа

Я написал ниже программу для извлечения последних пяти цифр n числа, которое является ответом функции ниже:

n = 1 ^ 1 + 2 ^ 2 + … + m ^ m

где м дается пользователем. Программа работает хорошо для небольшого числа, но она не будет работать для m, равного 100 ^ 100.

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
int n;

cin>>n;
intmax_t a[n],num,rem;
a[0]=0;
for (int i=1; i<=n; i++){

a[i] = a[i-1]+pow(i,i);
}

num=a[n];

int b[5];
for (int i = 1; i <=5; i++) {
rem = fmod(num,10);
b[i]=rem;
num = num/10;
}

for (int i = 1; i <=5; i++) {
cout<< b[i];

}
return 0;
}

1

algorithm bignum c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

«Получить последние пять цифр» означает мод 100000. На самом деле, 100 ^ 100 действительно мало. Вам не нужно использовать bignum в этом случае, так как (a * b) mod n = ((a mod n) * (b mod n)) mod n.

#include <iostream>
using namespace std;

int getLastDigits(int base, int pow, int numDigit) {
int divisor = 1;
for (int i = 0; i < numDigit; i++)
divisor *= 10;

int retVal = 1;
for (int i = 0; i < pow; i++) {
retVal *= base;
retVal %= divisor;
}

return retVal;
}

int main()
{
int n;

cin>>n;
int res = 0;
for (int i=1; i<=n; i++){
int tmp = getLastDigits(i,i,5);
//cout << tmp;
res += tmp;
}

cout << res % 100000;
return 0;
}

Для действительно большой, вы можете посмотреть на https://en.wikipedia.org/wiki/Modular_exponentiation

2