保持一個大數目

我已經寫了下面的程序提取的是以下功能的回答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; 
}

來源

2016-11-18 Lily bentham

【計算POW（A，B）MOD N]（可能的重複http://stackoverflow.com/questions/8496182/calculating-powa -b-mod-n） – ruakh

兩個問題：首先C++沒有[可變長度數組]（https://en.wikipedia.org/wiki/Variable-length_array）（有些編譯器把它作爲擴展，但請避免使用例如'std :: vector'）。其次，當你做'num = a [n];'你正在索引'a'出界。您的循環也將索引數組（包括'a'和'b'）越界。記住：數組索引是基於*零*的。 –

另外，'fmod'用於浮點類型 – George

「獲取最後五位數」意味着mod 100000.實際上，100^100確實很小。由於（a * b）mod n =（（a mod n）*（b mod n））mod n，所以在這種情況下不需要使用bignum。

#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

來源

2016-11-18 08:17:04

100^100比數字大10^120倍宇宙中的原子。不完全「非常小」。 – molbdnilo

我就這個問題說:)只有5個最後的數字，它永遠不會超過100000. –

和100^100 =（10^2）^ 100 = 10^200 @molbdnilo –

保持一個大數目

回答

相關問題