模函數只適用於整數數據類型嗎？

-2

我的算法計算下面給出的算術運算，爲它完美的小值，但對於大量的，如218194447它返回一個隨機值，我曾試圖用很長很長整型，雙，但沒有工作，因爲模函數我有使用只能用int型可以使用，任何人都可以解釋如何解決，或可提供可能是有用的一個環節模函數只適用於整數數據類型嗎？

#include<stdio.h> 
#include<math.h> 

int main() 
{ 
    long long i,j; 
    int t,n; 

    scanf("%d\n",&t); 

    while(t--) 
    { 
     scanf("%d",&n); 

     long long k; 
     i = (n*n); 
     k = (1000000007); 
     j = (i % k); 

     printf("%d\n",j); 
    } 

    return 0; 
}

來源

2014-09-01 user3315556

請縮進/格式化您的代碼，使其可讀。謝謝。 – 2014-09-01 19:12:19

可能重複： - http://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers – 2014-09-01 19:13:34

無關：只是用'1000000007'似乎比重新計算'戰俘相當清晰的（10,9 ）+ 7'，我們只能希望一個合理智能的編譯器進行優化。 – WhozCraig 2014-09-01 19:19:59

你可以聲明你的變量爲int64_t或long long;那麼他們將計算它們範圍內的模數（例如int64_t的64位）。只有所有中間值都適合其範圍，它才能正常工作。

不過，你可能想要或需要bignums。我建議你學習和使用GMPlib。

順便說一句，因爲它在浮點計算不使用pow。嘗試i = n * n;而不是i = pow(n,2);

^{P.S.這不是在C編程初學者，使用gmplib需要一定的流暢度C語言編程（和編程一般）}

來源

2014-09-01 19:27:06

在你的代碼的問題是，你計算的間歇值超過值的範圍可以存儲在一個int中。對於n> 2^30的值，n^2不能表示爲int。

請按照以上鍊接給R.T.在大數字上做模數的方法。這還不夠，因爲你還需要一個可以處理大整數值的類/庫。只有標準的C庫，否則這將是一項自己的任務。（好吧，對於2^31，64位整數可以，但如果你要變大，你又不幸運了）

來源

2014-09-01 19:25:10 PMF

接受後回答

爲了找到提高到一些權力一些n的模p（在OP的情況下爲2），則不需要第一個計算power(n,p)。相反，計算中間模數值爲n將提升至中等能力。

以下代碼與OP所需的p==2一起使用，但如果p=1000000000也可以快速工作。

唯一需要的更寬的整數是是兩倍寬n整數。

執行這一切都是無符號整數簡化了所需的代碼。

生成的代碼非常小。

#include <stdint.h> 

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) { 
    // `y = 1u % mod` needed only for the cases expo==0, mod<=1 
    // otherwise `y = 1u` would do. 
    uint32_t y = 1u % mod; 

    while (expo) { 
    if (expo & 1u) { 
     y = ((uint64_t) base * y) % mod; 
    } 
    expo >>= 1u; 
    base = ((uint64_t) base * base) % mod; 
    } 

    return y; 
} 

#include<stdio.h> 
#include<math.h> 

int main(void) { 
    unsigned long j; 
    unsigned t, n; 

    scanf("%u\n", &t); 

    while (t--) { 
    scanf("%u", &n); 

    unsigned long k; 
    k = 1000000007u; 
    j = powmod(n, 2, k); 

    printf("%lu\n", j); 
    } 

    return 0; 
}

來源

2014-10-15 22:10:42 chux

模函數只適用於整數數據類型嗎？

回答

相關問題