정수론은 솔직히 내가 살면서 탑코더 외에서 쓸 일이 없어서 공부를 잘 안하게 된다. [....] 사실 그래서 만인의 상식이어야 할 extended Euclid 따위도 필요할 때 찾아보지 않으면 모르고.. 그런 김에 위키피디아에서 의미있을 만한 정리를 긁어모아보려고 하는데 뭐가 있을까요? (제대로 공부하려면 concrete mathematics 라도 봐야하겠지만 아엉)
아래는 생각나는 대로.
- Euler's Theorem: a 와 n 이 coprime 일 때, a^phi(n) = 1 (mod n). phi() 는 Euler's totient function.
- Chinese Remainder Theorem: pairwise coprime 인 정수들의 벡터 n_i 와, a_j < n_j for all j 인 nonnegative 정수 벡터 a_i 가 있을 때, x_j % n_j = a_j 인 a_j 를 찾는다.
- Extended Euclidean Algorithm
- Lucas' Theorem: p 가 소수일 때, 이항계수 (m,n) 을 매우 큰 m,n 에 대해 빠르게 찾기.
다른 것 추천 좀 해주세요~ ㅠ
4는 GCJ에 한 번 나온듯여?? [(m,n) mod p 겠져?]
근데 진짜 다른게 있긴 있나 =_=; 정수론 수업 때 한건 많은데 막상 대회땐 딱히 특별한게 없는듯여...