컴퓨팅 합계 N

는 I 효율적 다음의 합계를 계산하기 바라는 , A < B이고 A와 B는 공동 소수입니다 (그렇지 않으면 쉬운 축소가 가능함). 숫자가 크기 때문에 간단한 반복은 너무 비효율적입니다. 지금까지는 다항식 시간 알고리즘 (즉, log (B)의 다항식)을 찾지 못했습니다. 가장 좋은 것은 O (sqrt (max))입니다. 이것은 알려진 어려운 문제입니까 아니면 다항식 시간 알고리즘을 알고 있습니까?컴퓨팅 합계 N

"mod B"는 전체 합계가 아닌 i * A에만 적용됩니다. 그래서 예.

합은 (i = 0..3) = (I 7 개조 11 *) 0 + 7 + 3 + 10 =

출처

2014-04-10 Henning Koehler

호기심에서 벗어나 O (sqrt (max)) 솔루션은 무엇입니까? –

조금 복잡하지만 요약하면 값의 선형 시퀀스 (최대 sqrt (최대))로 합계를 나눈 다음 각 선형 서브 시퀀스에 대해 합계를 위해 삼각형 규칙을 적용합니다. –

넌 얻을 조각 주위 물건을 이동할 수 20

A*(sum(i=0..max)) mod B

A*(max*(max+1)/2) mod B

로 단순화

이제 하나의 (큰 INT) 모드 작동을합니다 (최대 자체가 너무 크지도 않고 가정) 하나 (아마도 큰 int)를 곱셈을 할 필요가있다.

출처

2014-04-10 00:43:36 Penguino

여전히'(x * y) mod B = (x mod B) * (y mod B) mod B'라는 곱셈의 큰 하위 결과를 푸는 사실을 사용할 수 있습니다. –

미안하지만, 제 질문으로는 분명하지 않다고 생각합니다. 모듈로 B는 전체 값이 아니라 개별 값에만 적용됩니다. –

답변

관련 문제