Cómo calcular el módulo de la forma (a * b)% c?

Cómo calcular el módulo de la forma (a * b)% c?Cómo calcular el módulo de la forma (a * b)% c?

quiero para calcular el módulo de la multiplicación de dos números int donde están casi en la etapa de desbordamiento ...

aquí c también se int

Fuente

2011-05-06 Kunal

Puedes lanzar a y c-long long, por lo la multiplicación no se desbordará

((long long)a * (long long)b) % c

Fuente

2011-05-06 18:57:24 buc

tardará mucho tiempo – Kunal

necesito algo de método optimizado – Kunal

No creo que encuentre una solución más rápida. En las máquinas x86, el resultado de la multiplicación de 32 bits siempre es de 64 bits. De esta forma, simplemente notifica al compilador que use el resultado de 64 bits. – buc

(a * b) % c == ((a % c) * (b % c)) % c

Fuente

2011-05-06 19:04:54 kennytm

+1 Acabo de comenté esto, pero la falta de café significaba que no estaba seguro. ;) – Bart

Si a <= b Westy92

¿Qué hay de ((a % c) * (b % c)) % c? Dependiendo de su arquitectura, esto podría ser más rápido o más lento que lanzar a un tipo más grande.

Fuente

2011-05-06 19:04:56

Si a <= b Westy92

Cómo calcular el módulo de la forma (a * b)% c?

Respuesta

Cuestiones relacionadas