c++ - 保留一个大数字的一部分

Question

我写了下面的程序来提取 n 数的最后五位数字，这是下面函数的答案:

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

其中 m 由用户提供。该程序适用于小数，但不适用于 100^100 这样大的 m。

#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

“取最后五位”的意思是mod 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;
}

对于真正大的n，可以看看https://en.wikipedia.org/wiki/Modular_exponentiation