Lily bentham - 1 year ago 68

C++ Question

I have wrote below program to extract the last five digits of n number that is the answer of function below:

n = 1^1 + 2^2 + ... + m^m

where m is given by the user. The program works all right for small number but it will not work for m as big as 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;

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

"Get last five digits" mean mod 100000. In fact, 100^100 is really small. You don't need to use bignum in this case since (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;
}
```

FOr really big n, you can look at https://en.wikipedia.org/wiki/Modular_exponentiation

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**