와... 멀어만 보이던 루비를 드디어 달성했습니다. 군대를 7월 15일에 가서 군대 가기 전에 루비 찍고 가려했는데 그 목표를 달성했네요!!!! 이제 solved.ac 디코에서도 분홍색 닉네임입니다!! 꺄~~~~~~루비 가려고 마음 먹은게 루비까지 50점도 레이팅이 남았을 때였습니다. 그때는 클6이었는데 클8을 열심히 밀어서 레이팅 20을 얻었습니다. 이후 개꿀 날먹처럼 보이는 r5 문제를 2문제 정도 풀었는데 다 거짓말이었습니다;;;; 요즘 정수론을 안하고 있었는데 다시 하니까 너무 재미있었습니다. 특히, r5 위수는 쿼리입니까? 가 제일 인상 깊었습니다. 여기에서 구현해 놓은 것으로 한 d2 3개정도 날먹한거 같네요^^. 마지막으로 푼 문제는 coefficient 라는 페트로 문제인데 FFT 오차가 ..

오랜만에 찾아온 백준 포스팅이에요~! 7.15에 군대에 가는데 그 전에 루비를 찍고 가려고 열심히 문제 풀고 있습니다!최근에 클8도 따고 해서 루비까지 남은 레이팅은 21점!!! 남은 레이팅은 제가 좋아하는 정수론으로 채울겁니다!아 정수론 오랜만에 하니까 감이 좀 떨어진듯 하네요;; 일단 각 쿼리를 각각 처리해봅시다.  첫 번쨰 쿼리$N=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{t}^{r_{t}}$가 $N$의 소인수분해라고 합시다. 주어진 $a$에 대하여 $a^{e}\equiv 1\pmod{N}$을 만족하는 최소의 $e$를 찾기 위해서는 먼저 $\gcd(a,N)=1$이어야 합니다. $\gcd(a,N)=1$을 가정해두고 논의를 진행합시다. $a$의 위수를 찾기 위해서 다음 렘마를 사..

본 글은 다음 세 논문을 바탕으로 쓰여 있습니다. 우리는 크기가 $p\times q$, $q\times r$인 두 행렬을 곱하는 cost를 $pqr$이라고 생각합니다. 행렬 $M_{1}\times \cdots \times M_{n-1}$을 곱하는데 필요한 최소의 연산 횟수는 얼마일까요? $M_{i}$의 크기를 $w_{i}\times w_{i+1}$이라고 두고 $w_{1}$부터 시계 방향으로 꼭짓점에 $w_{i}$들을 할당하여 $w_{n}$으로 끝나는 아래의 볼록 다각형을 생각해봅시다. Part 1. Lemma 1에서는 위 볼록 다각형을 partition하는 것이 행렬들의 연산 순서와 대응된다고 합니다. 볼록 다각형의 partition의 cost는 partition으로 만들어지는 삼각형들의 각 가중치를 합..

새로운 유형을 도전해서 그런가 좀 어려운 문제였다. 우리는 1부터 $2^{64}-1$까지의 수를 모두 2진수로 표현할 수 있다. 그리고 진수로 표현된 자릿수를 이용해서 모든 수를 64-dimensional vector에 대응시키자. 우리는 각 bit의 자릿수에 대해서 xor 연산을 생각하기 때문에 base field가 $\mathbb{Z}/2\mathbb{Z}$인 64-dimensional vector space를 고려한다. 그렇게 된다면 덧셈이 곧 xor연산이 된다. 이제 Xorshift64 함수는 linear operator로써 작동하고 이에 대응되는 행렬 $M\in M_{64\times 64}(\mathbb{Z}/2\mathbb{Z})$를 생각할 수 있다. 이 행렬을 구하는 방법은 vector sp..

$a,b$ 둘 다 $p$의 배수라고 하면 자명하게 성립하므로 $(p-1)^{2}$개를 일단 찾았다. $a$나 $b$ 중에 1개만 modulo $p$로 0이라고 하자. 일반성을 잃지 않고 $b\equiv 0\pmod{p}$라고 한다면 $a^{b}\equiv 0\pmod{p}$이며 $p|a$이고 모순이다. 따라서 우리는 $a,b$ 둘다 $p$의 배수가 아닌 경우를 고려한다. 그럼 원시근 $g$에 대하여 $a\equiv g^{x}\pmod{p}$, $b\equiv g^{y}\pmod{p}$라고 대응시길 수 있고 $0\le x,y \le p-2$이다. 주어진 식을 다시 써보면 $xb\equiv ya\pmod{p-1}$이다. 우리가 $xb\equiv ya\pmod{p-1}$를 만족시키는 $a,b,x,y \pmod..

꽤나 대수학적 지식을 필요로 하는 문제이다. 문제에서 주어진 $S, T$를 그대로 활용하자. 그럼 다음이 성립한다. $$\begin{bmatrix} x_{n+1} \\ x_{n} \end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} x_{1} \\ x_{0} \end{bmatrix}$$ 그럼 \[ \begin{bmatrix} x_{S+T+1} \\ x_{S+T} \end{bmatrix}- \begin{bmatrix} x_{S+1} \\ x_{S} \end{bmatrix}= \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}^{S}\left( \begin{bmatrix} a & b \\ ..