2월 12일에 SUAPC 대비를 위한 팀연습을 치뤘다. 우리 팀 중 한 명은 갑작스럽게 잡힌 일정에 대비하지 못해서 대타 버스기사 kiwiyou를 데리고 팀연습을 치루었다. 상대 팀은 전 ICPC 팀메이트였던 changhw의 팀. 진짜 강적이었다... kiwiyou가 빡구현 문제, blackstar0223이 아이디어성이 높은 그리디 문제에서 승리하지 못했으면 내가 구멍이 되었을 것이다. 난... 3문제를 풀기는 했는데 발목에 추만 달아 준 느낌이라... 셋은 UCPC 2021 예선. 내가 B, F, G를, blackstar0223이 C, D를, 그리고 kiwiyou가 A, I를 잡아내서 7문제를 풀 수 있었다. 그런데 이거 3시간 셋을 억지로 5시간으로 늘린 거라 이 멤버로 했어도 본선은 못 갔을 것 같..

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

SUAPC 2023 Summer B번 문제이며, 내가 출제한 세 번째 문제이다. 출제 여담은 SUAPC 2023 Summer 출제 후기에 충분히 썼으니 이번에는 이 문제의 수학적인 해결법에 대해 논하고자 한다. 에디토리얼에 있는 풀이 두 가지 대신 출제 때부터 마음 속에 품고 있었던 야매 풀이 하나와 어제 생각해 낸 제4의 풀이 이렇게 두 가지로. 그럼 본격적으로 풀이에 돌입해 보자. 문제 행렬식은 선형대수학에서 다루는 기초적인 대상 중 하나이다. 이항계수는 조합론에서 다루는 기초적인 대상 중 하나이다. 두 기초적인 대상을 섞은 문제는 기초적이므로, 다음 행렬의 행렬식을 구하는 문제는 기초적인 문제이다. $$A(a_1,a_2,\cdots,a_N)=\left({a_i\choose {j-1}}\right)_..

모든 시험이 오늘부로 종료되었다. 성적이 나온 과목은 몇 개 있는데 하나는 생각보다 덜 만족스러웠다. 어쩌겠는가, 이미 안다고 자만하며 공부를 조금 소홀히 한 내 잘못이지. 이번 문제는 정수론적 지식이 매우 강력하게 필요한, 무려 다이아몬드 IV 문제이다. 소인수분해 과정에서 밀러-라빈과 폴라드-로까지 사용해야 하는 매우 복잡한 문제. 혹시 그 쪽에 대한 지식이 필요하다면, 이 포스트를 참조하라. 심지어 이 문제를 약간 발전시킨 문제는 루비 IV에 랭크되어 있다! 그 코드도 거의 다 만들었으나, 의문의 시간초과로 인해 난항이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 ..

아마 모두의 첫 다이아몬드 티어가 아닐까. 소수 판정법과 소인수분해에 관해서는 거의 마법이나 다름없는 두 가지 알고리즘을 잘 쓰면 된다. 밀러-라빈 소수판정법과 폴라드-로 소인수분해 알고리즘. 작동 방식만 알고 있으면 그리 어렵지 않게 풀 수 있다. 그 작동 방식을 이해하는 것이 최소 다이아몬드라는 것은 잊어 두자. 그럼 본격적으로 풀이에 돌입해 보자. 문제 큰 수를 소인수분해 해보자. 입력 입력은 한 줄로 이루어져 있고, 소인수분해 해야 하는 수가 주어진다. 이 수는 1보다 크고, \(2^{62}\)보다 작다. 예제 입력) 18991325453139 출력 입력으로 주어진 양의 정수를 소인수분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다. 예제 출력) 3 3 13 179 271 138..