이 문제는 서로 다른 두 소수 $p,q$에 대해서 $p^{1/n}+q^{1/m}(n,m\in \mathbb{N}_{\ge 1}$의 최소 다항식을 구하는 문제이다. 아래 두 개의 lemma를 증명하며 최소 다항식을 구하는 방법을 알아보자. $K$가 $F$의 field extension이라 하자. Lemma 1. $\forall \alpha \in K$, $\alpha$ acting by left-multiplication on $K$ is a $F$-linear transformation of $K$. Proof. 임의의 $x, y\in K$와 $a, b\in F$를 잡자. 그럼 $\alpha(ax+by)=\alpha ax+\alpha by = a(\alpha x)+b(\alpha y)$가 된다. 따라서 ..

원점에서 $(n,m)$으로 레이저를 쏘는 상황을 생각해보자. 집은 몇 개가 부숴질까? $y=\frac{m}{n}x$를 생각해보자. 이 직선에서 $x,y$가 모두 정수인 점이 집이 있는 구간이다. 결국 $mx=ny$의 정수 해의 개수가 된다. $(m,n)=d$라 하면 $m'=m/d,\ n'=n/d$ 일 때 $m'x=n'y$이고 따라서 $x=\alpha n',\ y=\alpha m'(1\le \alpha \le d)$이다. 그러므로 총 $d$개 의 집이 부숴진다. 원점도 집이 있으므로 $d+1$개 부숴진다. 벽을 지난다는 것은 무엇을 의미할까? 세로 벽을 생각하면 위에서 생각한 직선이 $(a,b)$와 $(a,b+1)$의 사이를 지난다는 것을 의미한다 그렇다는 것은 $b

굉장히 오랜만에 올리는 포스팅~ 방학동안 버클리에 가 있어서 백준을 못한게 크다 ㅜㅜ. 본론으로 들어가자. 문제는 $m$개의 재료 중에서 $n$개를 선택해서 그 값들의 곱을 모두 더하는 것이다!! 간단히 주어진 예제로 생각해보면 값이 각각 $x, y, z$라고 할 때 \[x^{3}+y^{3}+z^{3}+x^{2}(y+z)+y^{2}(z+x)+z^{2}(x+y)+xyx\] 를 구하는 것이다. 우리가 생각할 수 있는 것은 이 식을 어떻게 좀 간단하게 할 수 있냐는 것이다. 놀랍게도 위의 식은 다음과 같이 간단하게 표현된다! \[\frac{x^{5}}{(x-y)(x-z)}+\frac{y^{5}}{(y-x)(y-z)}+\frac{z^{5}}{(z-x)(z-y)}\] 값이 서로 다른 $m$개의 재료 중에서 $n$..

문제에서 주어진 조건으로부터 $(n,m)=1$이고 $m\not\equiv n\pmod{2}$라는 사실을 알 수 있다. 그럼 우리가 구하고자 하는 값은 다음과 같다. \[\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][n=odd][m=even]\] 위 식을 변형 시키면 다음을 얻는다. \[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1](1-[2|n])[2|m]\] \[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][2|m]-\sum_{n=1}^{L}\sum_{m=1}^{L}[(n,m)=1][2|n][2|m]\] 이때 오른쪽 항은 항상 0이 된다는 사실을 알 수 있다. \[=\sum_{n=1}^{L}\sum_{m=1}^{L}\sum_{s=1..

Yule lads라는 산타클로스(?)가 왜서 불을 끄고 키고 한다는 문제이다. 총 $N$개의 집이 있고 모두 불이 켜져있다. 크리스마스의 $n$째날 전에는 $n$의 배수 번째 집의 불이 꺼지고 마지막에 숫자 1을 제외하고 모든 집에 불이 꺼질 경우 몇 명의 Yule Lads가 올 수 있을까?를 묻고 있다. 이런 경우에는 소수를 먼저 보자. 소수 번째 집에는 반드시 YL(Yule Lad)이 와야한다. 그럼 서로 다른 소수의 곱 번째 집($pq$)에는 $p$가 한 번 왔다가고 $q$가 한번 왔다 가므로 $pq$는 반드시 들러야한다. 일반화해보면 $n$의 약수의 개수가 짝수 개이면 된다는 것이다. 그런데 소수의 제곱수들을 생각해보자. 이들은 약수가 홀수 개이므로 YL이 오지 않는다. 서로 다른 $n$개의 소수..

이 문제 역시 교육적인 문제. 부분 조건을 이용해 전체 조건을 만족시키게 하는 문제이다. 문제에서 주목할 부분은 $F_{n} \bmod{10^{13}} =N$이 되는 $n$이 있냐는 것이다. 다른 말로 하면 $F_{n}\bmod{10}=N\bmod{10}$이고 $F_{n}\bmod{100}=N\bmod{100}$이고 ...를 만족하는 $n$이 있냐는 것이다. 우린 modulo가 $10^{3}$인 곳에서 시작한다. 왜냐면.. 그때부터 피보나치 수열의 피사노 주기가 $10^{n-1}*15$이기 때문이다. 알고리즘의 작동 원리는 간단하다. 법 $10^{3}$에 대해 $i$번째 피보나치 수와 $N$이 합동인 $i$들을 모아놓자. 이론적으로 1500개만 검사하면 되므로 금방 모인다. 그럼 방금 구한 각각의 인덱스..