C++에서 큰 곱셈의 나머지 찾기

다음 문제에 관해 도움을 요청하고 싶습니다. 나는 두 개의 정수를 곱하고이 곱셈의 나머지를 특정 수 (즉, (x * y) % A)로 나눈 함수를 생성해야합니다.C++에서 큰 곱셈의 나머지 찾기

이 문제는 부호없는 long long int를 사용하지만 A = 15입니다! 이 경우 x와 y는 이전에 A로 계산됩니다. 따라서, x * y는 2^64 - 1보다 클 수 있으며 따라서 오버플로됩니다.

외부 라이브러리를 사용하고 싶지 않았습니다. 누구든지이 문제를 해결하기 위해 짧은 알고리즘을 설계하는 데 도움이 될 수 있습니까?

미리 감사드립니다.

2013-10-03 ddsLeonardo

이미 mod A와 x가있는 경우 사용하지 않으시겠습니까? 뭔가 같은 경우

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 오른쪽 훨씬 작아야한다?

편집 :

당신이 10e11 같은 많은 수의, 당신이 다른 방법을 사용해야 할 것 같아요 계수의 WRT를 찾으려고 노력합니다. 하지만 실제로는 효율적이지하면서,이 같은 당신이 코드와 설정을 이해한다면, 당신은 내가 그것을 사용하는 나머지

출처

2013-10-03 03:54:25 xcorat

을 알아낼 수 있어야하지만 나쁜 시나리오에서 그들이 할 수

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과 같아야하며,이 경우에는 곱셈이 오버플로됩니다. 는 I 시도 다음 '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; 0x35FFFFFFFFFF) >> 32; \t \t h [2] = (x & 0xFFFFFFFF) >> 16; \t \t h [3] = (x & 0xFFFF); \t \t 찾는 (나는 <4] I = 0 int로 난 ++) { \t \t \t \t \t 입술 = (입술의 + Y *의 H [I]) % A를; \t \t} \t \t return res; \t} \t return (x * y) % A; }' – ddsLeonardo

당신이 말한 것처럼 큰 숫자로 작업 할 수 있도록 실제로 편집했다고 말한 것을 잊었습니다. – xcorat

답변

관련 문제