본 글은 다음 세 논문을 바탕으로 쓰여 있습니다. 우리는 크기가 $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..

구해야 하는 것은 \[\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[ \gcd(Y_{a,b},Y_{c,d},Y_{e,f})=1]\] 이다. 뫼비우스 역변환을 이용하면 \[\sum_{s=1}^{359999}\mu(s)\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[s|Y_{a,b}][s|Y_{c,d}][s|Y_{e,f}]\] 이다. 그럼 우리는 $Y_{a,b}$이 각각 어떤 값을 가지고 얼마나 많은 중복이 일어나는지 세면 답을 구할 수 있다. 문제에서 $Y_{a,b}=X_{a}\times X_{b}\pmod{359999}$이다. 즉, $X_{a}$들의 범위는 $0~359998$이라 생각해도 무방하다. 특히, $359999 = 599 \times 601$로 CRT를 이용..