오랜만에 찾아온 백준 포스팅이에요~! 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 \\ ..

이 문제는 두 문제를 섞은 것이다. 그들은 각각 [BOJ 13716] 피보나치 수열처럼 보이지만... 과 [BOJ 17372] 피보나치 수의 최대공약수의 합 이다. 이 문제를 도전하기 전에 위 두 문제를 해결하고 오자. 앞서 포스팅에서 [BOJ 17372]를 다루었다. 그때와 같은 방식으로 본 문제에서 주어진 식을 단순화 하면 \[\sum_{d=1}^{n}d^{k}F_{d}C(d)\] 이며 $C(d)=2\sum_{i=1}^{n/d}\phi(i)-1$이다. [BOJ 17372]와 근본적인 방법은 똑같다. xudyh's sieve를 이용하여 $C(d)$를 빠르게 계산하고 $C(d)$에 $n/d$항이 존재한다는 특성을 이용해 $O(\sqrt{n})$만에 문제를 해결하는 것이다. 반면, 이를 위해서는 $\sum..