如果你已經有x和y的mod A,爲什麼不使用它們呢?像,
如果
x = int_x*A + mod_x
y = int_y*A + mod_y
然後
(x*y)%A = ((int_x*A + mod_x)(int_y*A + mod_y))%A = (mod_x*mod_y)%A
mod_x*mod_y
要小很多,對不對?
編輯:
如果你正在努力尋找模WRT像10e11
大一些,我想你將不得不使用另一種方法。不過,雖然沒有真正有效的,像這樣的工作
const int MAX_INT = 10e22 // get max int
int larger = max(mod_x, mod_y) // get the larger number
int smaller = max(mod_x, mod_y)
int largest_part = floor(MAX_INT/smaller)
if (largest_part > larger):
// no prob of overflow. use normal routine
else:
int larger_array = []
while(largest_part < larger):
larger_array.append(largest_part)
larger -= largest_part
largest_part = floor(MAX_INT/smaller)
// now use the parts array to calculate the mod by going through each elements mod and adding them etc
如果你瞭解這個代碼和安裝程序,你應該能夠找出休息
我使用它們,而是在一個糟糕的情況下,他們可以如10^11和10^10,在這種情況下,它們的乘法溢出。 我嘗試以下: 'LL big_num_mult(LL的x,LL Y) { \t如果(!Y = 0 && X> C/Y) \t { \t \t LL H [4],解析度= 0; \t \t h [0] = x >> 48; \t \t h [1] =(x&0xFFFFFFFFFFFF)>> 32; \t \t h [2] =(x&0xFFFFFFFF)>> 16; \t \t h [3] =(x&0xFFFF); \t \t對(INT I = 0; I <4;我++) \t \t { \t \t \t RES =(RES + Y * H [I])%A; \t \t} \t \t return res; \t} \t return(x * y)%A; }' – ddsLeonardo
忘了說我實際編輯過,以便它可以像你說的那樣使用大量數字。 – xcorat