시간 제한 메모리 제한 2 초 1024 MB 문제  $2$ 이상의 자연수 $N$과, $1$ 이상 $N-1$ 이하의 자연수 $a$에 대하여 $a^e\equiv 1\pmod{N}$을 만족시키는 가장 작은 $1$ 이상의 정수 $e$를 법 $N$에...

이전 글에서 이어진다. XOR convolution은 Cyclic convolution과 비슷하지만, 인덱스의 $+ \bmod N$이 아니라 $\oplus$ (bitwise XOR) 연산을 통해 정의된다. 즉, [(f \ast g)k = \sum{i \oplus j = k} f_i \cdot g_j \newcommand\widehatfix[1]{\...

이 글에서 수열과 벡터, 행렬 등은 특별한 언급이 없다면 0-index를 사용한다. Cyclic convolution은 주어진 길이 $N$의 두 수열 $f: f_0, f_1, \cdots, f_{N-1}$와 $g: g_0, g_1, \cdots, g_{N-1}$에 대해 [(f \ast g)k = \sum{\substack{i + j \equiv k...

일반적으로 선분 교차 판정은 CCW를 이용한 방법이 가장 유명하다. 그러나 그러할 경우 네 점이 일직선 위에 있는 등의 예외 케이스들을 처리해주기 어려운 문제가 있다. 이 글에서 다루는 것은 CCW를 이용한 풀이와 본질적으로는 같지만, 좀 더 논리적으로 예외 케이스를 추적하기 용이한 2x2 행렬을 이용한 풀이이다. 선분의 벡터 방정식 어떤 직선 $l...

2025년 7월 13일 어제 UCPC 예선이 있었다. 결과는 9+653/11로 15등, 본선 진출권에 들었다. 만족스러운 결과다..! 팀 구성 parkky, ssamt님이 팀원을 구한다고 하시길래 냉큼 들어갔다. 다들 너무 고수분들이라서 잘 할 수 있을지 걱정되기도 했다. SCP라는 팀명은 각자의 닉네임 이니셜을 따서 만들었다. 내가 만들었다😋...

때는 바야흐로 2025년 6월 11일. 일반화학 시험을 공부를 안 해간 나는 문제를 더 풀 수가 없었다. 심지어 조기 퇴실도 안 되는 시험이라 뭐 할지 고민하다가… 이산 제곱근 알고리즘을 구현해보기로 했다! …만, 당연히 시험 중이라 인터넷 검색도 안 되고 하니 그냥 직접 이산 제곱근을 구하는 알고리즘을 만들어보기로 했다. 이산 제곱근 말 그대로...

곱셈적 함수 정수를 정의역으로 갖는 함수 $f$가 서로소인 두 정수 $a, b$에 대해 $f(a)f(b) = f(ab)$를 만족할 때, 함수 $f$를 곱셈적이라고 합니다. 대표적인 곱셈적 함수로는 다음과 같은 함수들이 있습니다. $\mu(n)$: 뫼비우스 함수 $\tau(n)$: 약수 개수 함수 $\phi(n)$: 오일러 피 함수 $\...

수능 전까지는 바쁘게 살다가 수능 끝나고는 열심히 노느라 글을 이제야 쓰네요.. ㅋㅋㅋ 저는 수능을 잘 보긴 했는데 수시로 고려대를 붙어서 정시로는 KAIST에만 지원했고, 붙어서 지금은 KAIST에 다니는 중입니다. 엊그제 개강해서 벌써 강의를 열심히 듣고 있어요. 앞으로의 블로그 계획은 잠시 내려뒀던 PS를 다시 시작하면 PS 글도 쓸 것 같고,...

수능이 두 달도 채 남지 않았지만, PS는 계속됩니다… 시간 제한 메모리 제한 1 초 1024 MB 문제 나무에서 나뭇가지가 다 사라지면? 가지런하다 동우와 재우가 $1$번부터 $N$번 정점까지 총 $N$개의 정점으로 이루어진...

고3이라 바빠서 글 올리기로 해놓고 제대로 올리지도 못했습니다… 수능 끝나면 좀 더 열심히 해 보겠습니다 시간 제한 메모리 제한 2 초 1024 MB 문제 모든 격자점이 흰색으로 칠해진 좌표평면이 있다. 지호는 서 있는 점에서 $(x_i,...