1

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;
}
mindriot
  • 5,413
  • 1
  • 25
  • 34
narcis dpr
  • 939
  • 2
  • 12
  • 32
  • 1
    Possible duplicate of [Calculating pow(a,b) mod n](http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – ruakh Nov 18 '16 at 07:49
  • Two problems: First of all C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array) (some compilers have it as an extension, but please avoid it in favor of e.g. `std::vector` instead). Secondly, when you do `num=a[n];` you are indexing `a` out of bounds. Your loops are also indexing the arrays (both `a` and `b`) out of bounds. Remember: Array indexes are *zero* based. – Some programmer dude Nov 18 '16 at 07:50
  • Also, `fmod` is for floating point types – George Nov 18 '16 at 07:55
  • take a look at or google [modpow](http://stackoverflow.com/q/18577076/2521214) – Spektre Nov 18 '16 at 08:03

1 Answers1

2

"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

khôi nguyễn
  • 626
  • 6
  • 15