전체 글(77)
-
다이아몬드 달성!!!!!!
대부분 수학 문제라는 것이 함정 ㅋㅋ... 꾸준히 심어온 잔디에 빈칸이 생기는 슬픈 상황이 저번주에 발생했다. ㅜㅜ 스트릭 프리즈만 믿고 있었는데 알고보니 '적용하기'를 누르지 않았던 것...
2022.03.05 -
[BOJ 17105] 골드바흐 트리플
어떤 홀수가 주어질 때 그 홀수를 세 개의 소수의 합으로 나타내는 방법이 얼마나 많은지 구하는 문제이다. 주어진 홀수를 $n$이라 하자. 그럼 경우는 3가지가 있다. 각 경우마다의 경우의 수를 $a, b, c$라고 두자. 1. $n=p+q+r$ 2. $n=2p+q$ 3. $n=3p$ 가장 쉽게 생각할 수 있는 것은 소수 차의 항만을 가지며 계수가 1인 다항식 $P(x)$를 생각할 수 있다. 이 $P(x)^{3}$에서 $x^n$의 계수가 우리가 구하고자 하는 답과 가장 유사할 것이다. 하지만 그 계수는 $6a+3b+c$가 된다. $c$는 쉽게 구할 수 있으나 $b$를 구하는 것이 어렵다. $b$는 $P(x)$에서 각 항의 차수만 2배가 된 식 $Q(x)$와 $P(x)$를 곱하게 된다면 $x^n$의 계수로 ..
2022.03.04 -
128일 스트릭!!!
다이아 새싹을 얻었다! 2022.2.24
2022.02.25 -
[BOJ 16808] Identity Function
함수 $f$는 다음과 같이 정의된다. \[f(a)=a^{N} \pmod{N}\] \[F_{1}(a)=f(a)\] \[F_{k+1}(a)=F_{k}(f(a)) (k=1,2,3,...)\] 이를 간단히 하면 다음과 같다. \[F_{k}(a)=a^{N^{k}} \pmod{N}\] 이때 $F_{k}(a)=a$인 최소의 $k$를 찾는 것이 우리의 목표이다. 먼저 $N=p$(소수)일 경우를 생각해보자. \[a^{N^{k}} \equiv a \pmod{N}\] 이때 $gcd(a,N)=1$이므로 \[a^{N^{k}-1} \equiv 1 \pmod{N}\] \[N^{k} \equiv 1 \pmod{\phi(N)}\] 만약 이때 $\gcd(N,\phi(N))=1$이 아니라면 만족하는 $k$가 존재하지 않는다. $k$가 존..
2022.02.14 -
[BOJ 13714] 약수의 개수
위 문제에서 구하고자 하는 것은 다음과 같다. \[\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} \tau(ijk)\] 필요한 이론을 증명하고 문제를 해결하자. Theorm 1. \[\tau(ij)=\sum_{x|i} \sum_{y|j} [x \perp y]\] Lemma 1. \[n=\prod_{i=0}^{k} p_{i}^{a_{i}}t\ \ (p_{i} \nmid t)\] 일 때 다음은 $n$의 약수 중 $p_{i}$들의 배수의 개수이다. \[\prod_{i=0}^{k} a_{i} \tau(t)\] $i=p^{a}s(p \nmid s),\ j=p^{b}t(p \nmid t)$라 가정하자. \[\tau(ij)=(a+b+1)\tau(st)\] $s, t$가 서로소가 아니므..
2022.02.08 -
Modulo Prime Power Trick
이전에 조합을 소수의 $k$제곱으로 나눈 나머지를 구하는 방법을 소개했다. 그 방법은 너무 어렵기 때문에 조금 더 쉬운 방법을 소개한다. - Notation $(u!)_{p}$는 $u!$에서 $p$의 배수인 것을 제외한 곱을 의미한다. 소수 $p$와 자연수 $k$에 대하여 $p^{2k}$으로 나눈 나머지를 구한다고 하자. 이때 다음 식을 이용한다. \[\frac{(dp^{k}!)_{p}}{((d-1)p^{k}!)_{p}} \equiv (p^{k}!)_{p} \pmod{p^{2k}}\] 풀어서 써보면 다음과 같다. $p^{k}$와 서로소인 $p^{k}$이하의 자연수들의 집합을 $\{S\}$라고 하자. \[\prod_{a \in S} (dp^{k}+a) \equiv \prod_{a \in S} a \pmod..
2022.01.28