gcd와 xor의 성질, 연속하는 두 자연수는 서로소, dict보다 list를 먼저 고려하기

1. 문제

 

21004번: GCD vs. XOR (acmicpc.net)

21004번: GCD vs. XOR

 

2. 풀이

 

gcd(x,y)와 xor(x,y)가 서로 같게 되는 쌍 (x,y)의 개수를 구하는 문제

 

2-1) 먼저 gcd(x,y) = xor(x,y)가 되기 위한 특별한 조건을 이해해야한다.

 

gcd(x,y) = g이면, x = gp, y = gq이고 x-y = g(p-q)이다.

 

만약 x > y이면 p-q > 0이므로, $g \leq x-y$

 

다음, $xor(x,y) \leq x+y$이다. (직감적으로 맞는것 같은데 증명은 모르겠다...)

 

https://stackoverflow.com/questions/57118758/find-b-such-that-sum-of-a-b-is-equal-to-a-xor-b 

find b such that sum of a +b is equal to a xor b

 

https://stackoverflow.com/questions/36477623/given-an-xor-and-sum-of-two-numbers-how-to-find-the-number-of-pairs-that-satisf

Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?

 

즉, $(A xor B) xor B \leq (A xor B) + B$

 

여기서 xor연산은 결합법칙이 성립한다. 

 

https://namu.wiki/w/%EB%85%BC%EB%A6%AC%20%EC%97%B0%EC%82%B0#s-2.6

논리 연산 - 나무위키

 

그래서, $A xor (B xor B) \leq (A xor B) + B$

 

서로 동일한 값끼리 xor 연산을 하면 0이 된다.(실제로 해보면 0이 나옴)

 

$A xor 0 \leq (A xor B) + B$

 

0과 xor 연산을 하면 자기 자신이 나온다. 

 

$A \leq (A xor B) + B$

 

그러므로, $A - B \leq (A xor B)$

 

만약에 xor(A,B) = gcd(A,B)이면, $A-B \leq gcd(A,B) = xor(A,B) \leq A-B$이다.

 

그러므로, A-B = gcd(A,B) = xor(A,B)

 

그러면 n개의 원소가 있는 배열에서 두 수 A,B를 골라 gcd(A,B)와 xor(A,B)가 A-B가 되는지 검사해보면 될텐데..

 

이게 문제는 n이 최대 200만이라 $O(N^{2})$이면 20초더라도 바로 시간초과..

 

2-2) 이를 해결하기 위해 이해해야할 성질은 "연속하는 두 자연수는 서로소"

 

어떤 자연수 X에 대하여 X, X+1의 최대공약수를 g라고 하자.

 

X = gp이고 X+1 = gq이다.(p,q는 서로소)

 

그런데 두 수를 빼면 1 = gq - gp = g(q-p)

 

만약 g가 1이 아니라면 모순이다.

 

따라서 연속하는 두 자연수 X,X+1의 최대공약수가 1이므로 서로소이다.

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

최대공약수 g로 가능한 값은 1부터 배열 내의 최댓값까지 가능할 것이다.

 

이때 배열 내의 정수가 100만까지니까, 1부터 최대 100만까지 g를 순회한다.

 

여기서 어떤 정수 x에 대하여 gx와 g(x+1)을 잡으면 어떨까?

 

즉 g의 배수를 찾는 것이다.

 

그러면 gx와 gx+g의 차이는 무조건 g이기 때문에 gx와 gx+g의 xor연산을 수행해서, g가 되는지 확인만 해보면 된다.

 

그러면 1부터 배열 내의 최댓값 max까지 g를 순회하고 

 

x값을 1부터 max//g-1까지 순회하면 될 것이다. 

 

이러면 O(NlogN)인가??

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):

    n = int(stdin.readline())

    A = {}

    max_g = 0

    for i in map(int,stdin.readline().split()):
        
        if max_g < i:
            
            max_g = i
        
        A[i] = A.get(i,0) + 1

    count = 0

    for g in range(1,max_g+1):
        
        for x in range(1,max_g//g):
                            
            if g*(x+1) ^ g*x == g:
                
                count += (A.get(g*x,0) * A.get(g*(x+1),0))
          
    print(count)

 

배열의 원소를 순회하면서 최댓값 max_g를 찾고, 정수가 각각 몇개 있는지 dict에 저장을 해둔다.

 

그러면 g와 x를 순회하면서 g(x+1)과 gx의 xor이 g라면, 

 

배열 내의 gx와 g(x+1) 개수의 곱만큼 가능한 순서쌍이 존재할 것이다.

 

근데 이렇게 풀면 20초정도 걸리고

 

다른 사람들은 dict말고 list에 counting 배열을 만들어서 접근했는데 8초정도 걸리더라고

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):

    n = int(stdin.readline())

    max_g = 1000000
    
    A = [0]*(max_g+1)

    for i in map(int,stdin.readline().split()):
        
        A[i] += 1

    count = 0

    for g in range(1,max_g+1):
        
        for x in range(1,max_g//g):
                            
            if g*(x+1) ^ g*x == g:
                
                count += (A[g*x] * A[g*(x+1)])
          
    print(count)

 

 

리스트로 접근하나, dict로 접근하나 O(1)인데 dict 해싱 접근이 해싱 충돌 등등으로 시간복잡도가 더 클 수 있다는걸 본듯

 

이게 그 사례가 되겠네

 

그래서 특히 원소 수가 많을때(여기는 100만개) dict보다는 counting 배열로 접근을 하자