굉장히 오랜만에 블로그에 글을 쓰는 느낌이다. 대학원생이 된 이후로 바빠서 문제를 풀더라도 블로그에 글을 쓸 시간이 안 났다. 짬이 생긴 터라 오늘 푼 문제의 풀이를 작성한다.이 문제를 품으로서 수학 태그레이팅이 2600에 도달했다. 2700까지 올리고는 싶으나 아직 내가 그럴 만한 체급이 안 되는 것 같기도 하다. 천천히 올리자. 급하게 하지 말고.문제두 음이 아닌 정수 \(a,b\)에 대하여 \(a\wedge b, a\vee b\)는 각각 이들의 bitwise AND, bitwise OR를 나타낸다.음이 아닌 정수로 구성된 길이 \(2^N\)의 정수열 \(A_0,A_1,\cdots,A_{2^N-1}\)에 대해 \(A_i+A_j 입력첫째 줄에 음이 아닌 정수 \(N\)이 주어진다. \((0\le N\l..

요즘 수학에 관심이 있고 잘 하는 사람 몇 명이 solved.ac 디스코드에 모여서 같이 어려운 수학 문제를 썰고 있다. 나도 나름 수학을 잘 한다고 생각하지만, 당연히 세상은 넓다. 이제 자부심은 떼야 할 것 같다.그 디스코드 채널에서 나온 이야기다. 언제나처럼 두 명이서 수학 문제 관련된 이야기를 하고 있었는데, 조금 끔찍한 생각이 떠올라서 말을 꺼냈다. 그러고 나서 구현할 시간과 자신이 없어서 잠시 접어 뒀다가, 한 번 더 이야기를 꺼내고 구현을 시작했다. 아무리 봐도 답이 안 나와서 내가 망하고 있을 때 다른 분이 구현 된다고 검증하고 나서 디스코드에서 핑을 찍었다. 정작 나는 오타나 구현 오류 잡는다고 그 핑을 못 봤다. 1시간 정도 지나서 결정적인 오타 하나를 잡아낸 것 같다.누구에게서 문제 ..

백준에는 가끔씩 농도가 너무 높은 수학 문제들이 올라온다. 구현보다는 수학에 강점이 있는 나에게는 그런 문제들이 아주 맛 좋은 먹잇감이다. 오늘의 문제인 쉬운 문제도 그러하다. 글을 쓰는 지금 기준 Diamond III이라는 정말 높은 난이도를 자랑하지만 내가 이 문제를 보고 구현을 마치기까지 걸린 시간은 1시간도 안 걸렸다. 그렇다고 단체로 착각해서 이 문제를 어렵게 봤다는 말은 아니다. 제목 값을 전혀 하지 못하는 문제 중 하나라고 감히 자부까지 할 수 있다. 다만 이 문제의 풀이법이 KMO에서는 너무나도 웰노운이었을 뿐... 그럼 본격적으로 풀이에 돌입해 보자. 문제 1보다 큰 정수 \(k\)가 주어졌을 때, 다음 식을 만족하는 양의 정수 \((a, b, c)\)는 무수히 많다는 것을 증명할 수 있..