수학(29)
-
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 -
Mobius Inversion
\[f(n) = \sum_{d|n} g(d)\] 이라고 하자. 이때 $g(n)$의 값을 구하고 싶다. 이때 적용되는 식이 뫼비우스 역공식이다. \[g(n)= \sum_{d|n} f(d)\mu(\frac{n}{d})\] $f$가 곱셈적 함수이고 $f(n) = \sum_{d|n} g(d)$이면 $g$ 역시 곱셈적 함수이다. Notation $[P=k]$ : $P=k$일 때 1 아니면 0 $\epsilon(n)$ : $[n=1]$ $\sum_{d|n} \mu(d) =\epsilon(n)$ $\tau(n)$ : $n$의 약수의 개수 $a \perp b$은 $\gcd(a,b)=1$라는 뜻 \[1.\ \ \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i, j)\] \[\sum_{d=1}^{\min(..
2022.01.23 -
조합 더하기
보호되어 있는 글입니다.
2021.12.20 -
중복 조합
$a_{1}+a_{2}+...+a_{k}=d$이고 $0 \le a_{i} \le m$인 $a$에 관한 순서쌍의 개수를 찾고싶다! 예를 들어서 다음 경우를 보자. $a+b+c=15$이고 $m=9$ 기본적으로 전체 경우에서 망한 경우를 뺀다고 생각해보면 전체 경우는 $_{3}H_{15}$이다. 망한 경우는 $a$또는 $b$또는 $c$가 10이상인 경우로 $a$가 10이상이라고 생각한다면 $a^{\prime}+b+c=5$ 즉, $_{3}H_{5}$가 되고 $b$ ,$c$도 마찬가지이므로 $_{3}C_{1}$을 곱하여 망한 경우는 $_{3}C_{1}*$$_{3}H_{5}$가 된다. 따라서 구하고자 하는 경우의 수는 $_{3}H_{15}-$$_{3}C_{1}*$$_{3}H_{5}=73$이다. 이제 여러분은 계산할..
2021.11.07 -
정n각형의 대각선
$n$이 자연수인 $k$에 대해 $n=2k+1$임을 만족한다고 하자. 이때 정$n$각형의 한 꼭짓점을 $a_{1}$이라 하고 반시계 방향으로 꼭짓점을 $a_{i}$ ($i=2,3,...,n$) 라고 하자. 이때 $\overrightarrow{a_{1}a_{2}}$를 $\vec{a}$, $\overrightarrow{a_{1}a_{n}}$을 $\vec{b}$라고 하자. 정$n$각형의 한 변의 길이는 1이며 $\overline{a_{1}a_{i}}=r_{i-2}$라고 하자. 이때 $\overrightarrow{a_{k+1}a_{k+2}}$를 $\vec{a}$, $\vec{b}$로 나타내보자. 이 문제 해결의 아이디어는 순서대로 내려가는 것이다. 위 그림에서 $\vec{b}$의 한칸 아래인 $\overrigh..
2021.10.09 -
수열의 나머지
서로소인 자연수 $a,b$에 대해 수열 $F_{n}=aF_{n-1}+bF_{n-2}$에 대해 초항 $F_{0}=0, F_{1}=1$이면 $\gcd(F_{n},F_{m})=F_{\gcd(n,m)}$이다. 이것을 증명해보자. $F_{m} | F_{qm}$ 임의의 정수 $n$과 $p$에 대해 $F_{n-2} \equiv 0 \mod{p}$라고 하자. $F_{n} \equiv aF_{n-1} \pmod{p}$ $F_{2}=a$이므로 다음과 같이 바꿔쓸 수 있다. $F_{n} \equiv F_{2}F_{n-1} \pmod{p}$ 일반적으로 다음과 같이 쓸 수 있다.(이 아래에 나올 성질을 참고하자.) $F_{n+k} \equiv F_{2+k}F_{n-1} \pmod{p}$ $k=n-4$라고 하자. $F_{2n-4..
2021.09.19