Сохраняя часть большого числа

Question

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

п = 1^1 + 2^2 + ... + m^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; 
} 

Answer 1

«Получить последние пять цифр» означает модель 100000. Фактически, 100^100 действительно мало. В этом случае вам не нужно использовать bignum, так как (a * b) mod n = ((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; 
} 

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