n과 소수 p가 매우 클 때 wilson's theorem와 fermat's little theorem을 이용한 n! mod p 구하기

https://en.wikipedia.org/wiki/Wilson%27s_theorem Wilson's theorem - Wikipedia From Wikipedia, the free encyclopedia Theorem on prime numbers In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multip en.wikipedia.org https://namu.wiki/w/%EC%9C%8C%EC%8A%A8%EC%9D%9..

• format_list_bulleted 정수론
• · 2023. 8. 5.
• textsms

n이 매우 큰데 p가 매우 작은 경우에 효과적으로 n! mod p을 계산하는 방법

Factorial modulo p - Algorithms for Competitive Programming (cp-algorithms.com) Factorial modulo p - Algorithms for Competitive Programming Factorial modulo $p$ In some cases it is necessary to consider complex formulas modulo some prime $p$, containing factorials in both numerator and denominator, like such that you encounter in the formula for Binomial coefficients. We consider the case when c..

• format_list_bulleted 정수론
• · 2023. 8. 4.
• textsms

n차 다항식 함숫값 빠르게 계산하기(페르마의 소정리로 거듭제곱 빠르게 계산하기)

1. 문제 25025번: 다항식 계산 (acmicpc.net) 25025번: 다항식 계산 첫 번째 줄에 두 정수 $N$, $P$ ($0 ≤ N ≤ 10^6$, $1 ≤ P ≤ 10^3$, $P$는 소수)가 공백 하나로 구분되어 주어진다. 두 번째 줄에는 $N+1$개의 정수 $a_N$, $\cdots$, $a_1$, $a_0$ ($0 ≤ a_i ≤ 10^9$)가 공백 하나로 www.acmicpc.net 2. 풀이 결국에 구해야하는 값은 $a_{i}k^{i} mod P$이고 k와 P가 서로소이므로 페르마의 소정리를 이용할 수 있다. 그런데 1초안에 P개의 값을 계산해야하니 이거 쉽지 않다 계수는 최악의 경우 $10^{6}$개이고.. 매 함숫값마다 이들을 모두 순회해야하니.. $O(10^{9})$는 돌아야겠는..

• format_list_bulleted 정수론
• · 2023. 7. 8.
• textsms

이항계수를 소수로 나눈 나머지 구하는 방법 - Lucas' Theorem 배우고 적용하기

https://en.wikipedia.org/wiki/Lucas%27s_theorem Lucas's theorem - Wikipedia From Wikipedia, the free encyclopedia In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} by a prime number p in terms of the base p expansions of the integers m and n. en.wikipedia.org 1. Lucas' Theorem 정수 m,n과 소수 p에 대하여 $$\binom{m}{n..

• format_list_bulleted 정수론
• · 2023. 7. 4.
• textsms

피보나치 수열 심화과정5 -피보나치 수열의 합을 가장 빠르게 구하는 방법-

1. 피보나치 수열 $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1}+F_{n-2}, n \geq 2$로 정의되는 수열 $F_{n}$ 2. 홀수번째 항의 합 1항부터 $2n-1$번째 항까지의 합은 다음과 같이 $2n$번째 항과 동일하다. $$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$ 증명) $F_{n+2} = F_{n+1} + F_{n}$에서 n = 2n - 2를 대입하면, $F_{2n} = F_{2n-1} + F_{2n-2}$ 그러면, $F_{2n-1} = F_{2n} - F_{2n-2}$이므로, $$\sum_{k=1}^{n} F_{2k-1} = F_{1} + \sum_{k=2}^{n} (F_{2k} - F_{2k-2})$$ 이 식을 풀어서 써보면, 망원급수임..

• format_list_bulleted 정수론
• · 2023. 5. 27.
• textsms

숫자를 안만들고 나머지를 구하는 방법, 문자열 연산 없이 두 수를 붙이는 방법

1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..

• format_list_bulleted 정수론
• · 2023. 5. 8.
• textsms