TA貢獻1848條經(jīng)驗 獲得超10個贊
這些大量模量任務(wù)的關(guān)鍵是在執(zhí)行模量之前不計算全部結(jié)果。您應(yīng)該在中間步驟中減小模數(shù)以保持數(shù)量?。?/p>
500! / 20! = 21 * 22 * 23 * ... * 500
21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200
4475671200 mod 1000000007 = 475671172
475671172 * 28 mod 1000000007 = 318792725
318792725 * 29 mod 1000000007 = 244988962
244988962 * 30 mod 1000000007 = 349668811
...
31768431 * 500 mod 1000000007 = 884215395
500! / 20! mod 1000000007 = 884215395
您無需在每一步都減少模量。只要經(jīng)常做就足以防止數(shù)量過大。
請注意，的最大值long為2 ^ 63-1。因此，在兩個正整數(shù)值（即其中一個操作數(shù)為a long）之間執(zhí)行64位乘法運算不會溢出long。之后，您可以安全地執(zhí)行余數(shù)運算%（如果也為正數(shù)），并在需要時轉(zhuǎn)換為整數(shù)。
TA貢獻1799條經(jīng)驗 獲得超6個贊
首先，觀察一下這500!/20!是21到500之間的所有數(shù)字的乘積，包括端點和下一個。接下來，觀察您可以逐項執(zhí)行模乘，%1000000007并在每個運算的末尾進行。您現(xiàn)在應(yīng)該可以編寫程序了。注意不要使數(shù)字溢出：32位可能還不夠。
TA貢獻1775條經(jīng)驗 獲得超11個贊
我認為這可能對您有用
for(mod=prime,res=1,i=20;i<501;i++)
{
res*=i; // an obvious step to be done
if(res>mod) // check if the number exceeds mod
res%=
舉報