정수론 - 방정식을 만족하는 순서쌍의 수 세기 - 브루트포스 탐색 범위 줄이는 테크닉 익히기

1. 문제

 

C - Four Variables (atcoder.jp)

C - Four Variables

 

2. 풀이1

 

당연히 안될 것 같지만 방법을 모르겠다면 브루트포스로 접근하는게 기본이다

 

AB+CD = N을 만족하는 양의 정수쌍 A,B,C,D를 찾기 위해 1부터 N까지 순회해본다

 

이 값을 AB = x라 하고, 그렇다면 CD는 자동으로 N-x로 결정된다

 

그리고 AB = x에서 1부터 x까지 순회해서 그 수를 A라 하고, 만약 x가 A로 나누어 떨어진다면 B를 찾은 것이다.

 

마찬가지로 CD=(N-x) = y에서 1부터 y까지 순회해서 그 수를 C라 하고, 만약 y가 C로 나누어 떨어진다면 C를 찾은 것이다.

 

여기서 1부터 x까지가 아니고 $\sqrt{x}$까지가 아니냐? 하지만... 그건 A > B일때이고 여기서는 A < B여도 개수를 세야하니까 x까지 순회해야한다

 

n = int(input())
 
count = 0
 
for x in range(1,n):
    
    y = n-x
 
    for a in range(1,x+1):
        
        if x % a != 0:
            
            continue
        
        else:
 
            for c in range(1,y+1):
                
                if y % c == 0:
                    
                    count += 1
 
print(count)

 

 

근데 $O(N^{3})$이라 어림도 없다.

 

 

3. 풀이2

 

조금 머리를 써서 AB = x에서 (A,B) 쌍을 세서 count1이라 하고, CD = y에서 (C,D) 쌍을 세서 count2라 하면...

 

count1 * count2는 AB+CD = N을 만족하는 (A,B,C,D)의 개수가 된다

 

n = int(input())
 
count1 = 0
count2 = 0
count = 0
 
for x in range(1,n):
    
    y = n-x
 
    for a in range(1,x+1):
        
        if x % a == 0:
            
            count1 += 1
 
    for c in range(1,y+1):
        
        if y % c == 0:
            
            count2 += 1
    
 
    count += (count1*count2)
    count1 = 0
    count2 = 0
 
print(count)

 

이러면 O(N * (N+N))이라 $O(2N^{2})$이라 조금 빨라도 여전히 느리다

 

 

4. 풀이3

 

더욱 머리를 써서... AB=x를 만족하는 (A,B)의 개수는 결국 x의 약수의 개수와 같다

 

x의 약수의 개수는 x의 (소인수 지수+1)의 곱과 같다.

 

따라서 1부터 n-1까지 순회해서 x를 AB라 하고 N-x를 CD라 하자.

 

x를 소인수분해 해서 (소인수 지수+1)의 곱을 구해 AB의 쌍의 개수를 구하고

 

N-x를 소인수분해 해서 (소인수 지수+1)의 곱을 구해 CD의 쌍의 개수를 구한다

 

그러면 두 개수의 곱이 (A,B,C,D)의 개수가 된다

 

def prime_factorization(n):
    
    answer = 1

    p = 2

    count = 0

    while p*p <= n:
        
        while n % p == 0:
            
            n = n // p
            count += 1
        
        p += 1
        answer *= (count+1)
        count = 0
    
    if n > 1:
        
        answer *= 2
    
    return answer

n = int(input())

count1 = 0
count2 = 0
count = 0

for x in range(1,n):
    
    y = n-x

    count1 = prime_factorization(x)
    count2 = prime_factorization(y)
    
    count += (count1*count2)
    count1 = 0
    count2 = 0

print(count)

 

이러면 $O(2N*\sqrt{N})$인가..? 

 

아무튼 이러면 시간안에 통과한다

 

 

5. editorial solution1

 

AB+CD = N에서 AB = X로 고정시키면, CD = N-X로 자동으로 결정된다

 

마찬가지로 A가 결정되면 B가 자동으로 결정되고 C가 결정되면 D가 자동으로 결정된다

 

그러므로 가장 첫번째 제시한 솔루션으로 $O(N^{3})$으로 X,A,C를 찾으면 답을 구할수는 있다

 

그런데 두번째 제시한 솔루션으로 AB = X인 (A,B)를 구하고 CD = N-X인 (C,D)를 구한 다음에 경우의 수 곱의 법칙으로 $O(N^{2})$에 구할 수 있음을 보였다

 

여기서 더 나아가서, A <= B이면 AB = X를 만족하는 A의 최댓값은 $\sqrt{X}$이므로 1부터 X의 제곱근 까지 순회해서,

 

AB를 나눠보고 나누어 떨어진다면 count + 1을 해준다.

 

이 경우, A < B인 경우만 셌으므로 count + 1을 더 해주어서 A > B인 경우도 해준다.

 

A = B인 경우는 오직 1가지만 존재하므로 count + 1을 추가적으로 하지 않는다

 

이러면 $O(N\sqrt{N})$에 문제를 해결할 수 있다

 

n = int(input())
 
count1 = 0
count2 = 0
count = 0
 
for x in range(1,n):
    
    y = n-x
 
    for a in range(1,int(x**(1/2))+1):
        
        if x % a == 0:
            
            count1 += 1
 
            if x != a*a:
                
                count1 += 1
        
    
    for c in range(1,int(y**(1/2))+1):
        
        if y % c == 0:
            
            count2 += 1
 
            if y != c*c:
                
                count2 += 1
    
 
    count += (count1*count2)
    count1 = 0
    count2 = 0
 
print(count)

 

 

6. official solution2

 

AB = X를 만족하는 (A,B)의 개수는 결국 X의 약수의 개수이다.

 

x를 약수로 포함하는 어떤 정수들은 x, 2x, 3x, ... 로 x의 배수이다.

 

그러므로 길이 N인 counting 배열에서 x = 1, 2, 3, ..., N에 대해 N이하의 x의 모든 배수에 +1을 해주면 된다.

 

그러니까 N이하의 x,2x,3x,... 들은 (A,B) = (1,x), (2,x), (3,x), ...가 되는 것이다.

 

그리고 이들의 곱 x,2x,3x,..는 N이하이므로, AB+CD = N의 조건에 만족한다

 

(정답 개수 셀때는 N-1까지만 사용)

 

모든 경우를 순회하면 해당 배열의 index는 index의 약수의 개수가 된다.

 

이 때, CD = N-X이므로 counting[X] * counting[N-X]의 합이 정답

 

이 풀이가 놀라운 점은 AB = X를 만족시키는 (A,B)를 구하기 위해 X를 고정시켰는데

 

X를 고정시키지 않고 A,B를 각각 순회해서 (A,B)를 구한다는 점이다 

 

n = int(input())
 
ab_list = [0]*(n+1)
 
for x in range(1,n):
 
    for i in range(1,n//x+1):
        
        ab_list[i*x] += 1
    
answer = 0
 
for i in range(1,n):
    
    answer += (ab_list[i]*ab_list[n-i])
 
print(answer)

 

 

7. 최적화

 

바로 위 풀이에서 최적화할려면, AB = X에서 A <= B를 가정하고, 이럴 때 A의 최댓값은 $\sqrt{X}$

 

A를 1부터 $\sqrt{X}$까지 순회하여 a라고 한다면,  A < B이므로, B는 a부터 X까지 순회한다.

 

그리고 ab가 N보다 커지면 counting 배열에 표시하지 말고 a == b이면 1만 증가시키고 a != b이면 2를 증가시키고

 

n = int(input())

ab_list = [0]*(n+1)

for a in range(1,int(n**(1/2))+1):
    
    for b in range(a,n):
        
        if a*b > n:
            
            break

        if a == b:
            
            ab_list[a*b] += 1
        
        else:
            
            ab_list[a*b] += 2

count = 0

for i in range(1,n):
    
    count += (ab_list[i] * ab_list[n-i])

print(count)