[Codeforces 1151B] Dima and a Bad XOR - 1600 문제 설명 : n by m 크기의 행렬이 주어진다. 행렬의 각 열에서 임의의 숫자를 하나씩 뽑아서 xor를 취한다. 그 결과가 0이 나오지 않는 경우가 있다면 각 열에서 몇 번째 수를 xor해야하는지 출력하고, 아니면 반드시 결과가 0이 나올 수 밖에 없는지 구하는 문제이다. 풀이 : xor연산의 간단한 특성을 알아야 한다. a ^ b =0 을 만족한다면 a = b도 반드시 만족한다. 또한 a^b = 0 이고 b≠c라면, a^c ≠ 0 도 반드시 성립한다.이 두 가지 성질을 가지고 문제를 풀자. 이 문제에서의 관건은 어떤 수들을 xor해야 0이 나오지 않게 만드냐이다. 처음에는 일단 각 열의 첫 번째 원소들(mat[i][1]..
[Codeforces 1011E] Border - 1800 문제 설명 : 각 금액별 banknote가 충분히 많이 있다. 이 banknote들을 적당히 조합하여 만들 수 있는 정수들의 경우의 수를 구하는 문제이다. 풀이 : 베주 항등식을 활용하는 문제이다. 베주 항등식이란 두개 이상의 정수들의 최대공약수는 그 수들의 정수 곱으로 반드시 표현될 수 있다는 이론이다. 증명은 어려우니깐 패스하고 그냥 가능한가보다 라고 생각하겠다. 이 문제의 관심사는 각 banknote의 금액(a_i)를 k로 나머지 취한 값들을 적절하게 정수배하여 만들 수 있는 모든 금액의 경우의 수를 구하는 것이다. 주의할 점 : - 배운 점 : n개의 수들을 적절히 정수배한 값의 합의 모든 경우의 수를 구하기 위해서 베주 항등식을 활용하였..
[Codeforces 1025B] Weakened Common Divisor - 1600 문제 설명 : 문제에서 WCD라는 연산을 정의한다. 이 연산은 양의 정수 2개로 구성된 pair가 총 n개 주어질 때 두 수 중에서 최소 1개는 나누어 떨어지는 공약수를 전체 n개의 pair에 대해서 찾을 수 있으면 그 공약수를 구하거나 불가능함을 밝히는 문제이다. 풀이 : pair가 최대15만개 주어지므로 숫자는 총 30만개이고 각 수의 최대 범위는 20억이다. naive하게 생각하면 30만개 수를 모두 소인수분해해서 그 수들의 공약수를 찾으면 되는데, 소인수분해 알고리즘의 시간복잡도는 단발성 소인수분해는 O(sqrt(RANGE)), 전처리 소인수분해는 O(N*RANGE*log(log(RANGE)))이다(RANGE..