브 루트 포스 방지 : 계수 솔루션 프로그래밍 대회에서

Question

는 문제가 있었다 : 방정식

카운트 모든 솔루션 : x + 4y + 4z = n. 귀하는 이고 주어진 숫자는 n이며 솔루션 수를 결정하게됩니다. x, y 및 z는 양의 정수라고 가정합니다.

나는 루프 (무차별 공격)를 위해 트리플을 사용하는 것을 고려해 보았지만, 시간이 지나치게 길어서 불충분했다. (n = 1000,000 일 수 있기 때문에) :

int sol = 0; 
for (int i = 1; i <= n; i++) 
{ 
for (int j = 1; j <= n/4; j++) 
{ 
    for (int k = 1; k <= n/4; k++) 
    { 
     if (i + 4 * j + 4 * k == n) 
     sol++; 
    } 
} 
} 

내 친구가 문제를 해결할 수 있습니다. 내가 그에게 물었을 때, 그는 그가 무차별 대수를 전혀 사용하지 않는다고 말했다. 대신 방정식을 '계열'(즉, 합산)으로 변환했습니다. 나는 그가 어떻게 거절했는지에 관해 물어 보았다. 그러나 그는 거절했다. :)

나는 그것을 알 수 있냐?

Answer 1

이것은 일반적으로 동적 프로그래밍에 의해 해결되는 coin change problem의 특별한 경우입니다.

하지만 여기서 우리는 간단한 해결책을 자세히 설명 할 수 있습니다. I는 X 고려, Y, Z> 0

X + 4 * (Y + Z) = N 하자 Y + Z = Q = P + 1 (Q> 1, p> 0)

X + 4 * Q = N

X + 4 * P는 = N-4

가된다 M = 층 ((N-5)/4) X와 P를위한 변형, 따라서 거기 M 가능한 값 q = 1 + (q-1) = 2 + (q-2) + .. + q + 1의 (q-1) (q-1) +1

그래서 우리는 N = 1 + 2 + 3 + ...M + = 의 M * (M + 1)/2 솔루션

예 :

N = 15;

M = (15-5) = 2 4 DIV

N = 3

(3,1,2), (3,2,1), (7,1,1)

Answer 2

이것은 고전적인 선형 대수 문제입니다. 선형 방정식 시스템을 푸는 방법에 대해서는 선형 대수학 교과서를 참조하십시오. 그러한 방법 중 하나는 Gaussian Elimination입니다.

Answer 3

n-x은 4으로 나눌 수 있어야합니다. x이 취할 수있는 가장 작은 값을 찾아 시작 : 지금부터

start = 4 
while ((n - start) % 4 != 0) 
{ 
    start = start + 1 
} 

, 당신은 x이 [start, start+4, start+8 ...]에서 값을 가질 것이라는 점을 알고있다. 이제 간단한 계산 루프에 의해 솔루션의 수를 셀 수 : x의 각 선택에 대한

count = 0 

for (x = start; x < n - 4; x = x + 4) 
{ 
    y_z_sum = (n - x)/4 
    count = count + y_z_sum - 1 
} 

, 우리는 y+z의 값을 계산할 수 있습니다. y+z의 각 값에는 y이 1에서 y+z-1까지이므로 y과 z이 모두 양의 정수인 것으로 가정하여 y+z-1 개의 가능한 선택 사항이 있습니다.

실행 시간이 O (n) 인 무차별 대용 솔루션 대신 O (n)을 사용할 수 있습니다.