조만간 2020.05.11(?) problem solving이 올라옵니다. 그 글의 일부였는데, 좀 길어서 분리했습니다. https://www.acmicpc.net/problem/17405 Step 1 $gcd(F_i, F_j)$ 자체가 너무 커서 주어진 식 그대로는 다항 시간에도 계산을 할 수 없습니다. 하지만, $gcd(F_i, F_j) = F_{gcd(i, j)}$ 임이 잘 알려져 있기 때문에, 이 식을 쓰면 문제는 $\sum_{i = 1}^{n} \sum_{j=1}^{n} gcd(i, j)^k F_{gcd(i, j)}$ 가 됩니다. 항의 계산 결과가 gcd에만 의존함에 주목하십시오. $f(k) = 1 \le i, j \le N, gcd(i, j) = k$ 인 $i, j$ 의 수라고 하면, 위 식은..
소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 "어려운" 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다 빠른 알고리즘을 찾는 것은 쉽지 않다. 일반적으로 가장 자주 사용되는 알고리즘은 Pollard-rho라는 알고리즘이다. 이 알고리즘은 대회에 사용될 수 있을 정도로 복잡하지 않고, 평균 $O(N^{1/..
(9/30 초판) (9/30 ~ 10/10 PDF 연습 문제 17/22개 해결. 나머지는 시험 끝나고 시작할 것 같습니다.) (자료 출처는 이 사이트 내부 어딘가. 난 혜아한테 받아서 잘 모른다) 수학적 귀납법이란? 어떠한 명제 $P(1), P(2), P(3), \cdots$ 가 다음 두 성질을 만족한다고 하자. * (기저 조건) $P(1)$ 이 참이다. * (귀납 조건) $n \geq 1$ 일 때, $P(1), P(2), \cdots P(n)$이 참이면, $P(n+1)$이 참이다. 그렇다면 $P(1), P(2), P(3), \cdots$가 모두 참이다. 왜? 사실 위에 적은 수학적 귀납법을 "강한 수학적 귀납법" 이라고 부르고, 조금 더 약한 폼의 수학적 귀납법을 "수학적 귀납법" 이라 한다. 진짜 "..
- Total
- Today
- Yesterday