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

디오판토스 분수방정식의 정수 해법 배우기(+팩토리얼 인수분해, 제곱수의 약수의 개수)

1. 문제1 7516번: 알렉산드리아의 디오판토스 (acmicpc.net) 7516번: 알렉산드리아의 디오판토스 알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오 www.acmicpc.net 2. 풀이 주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면, $$\frac{y+x}{xy} = \frac{1}{n}$$ 이다. 그래서 $$n(y+x) = xy$$ 를 얻는다. 솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..) $n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다. 그리고..

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

팩토리얼을 계산하지 않고도 소인수분해하는 기본기

1. 문제 15996번: 팩토리얼 나누기 (acmicpc.net) 15996번: 팩토리얼 나누기 음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1) www.acmicpc.net 2. 풀이 n의 범위가 $2^{31} = 2147483648$까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니 계산하지 않고 $A^{k}$로 나눠보라는 말일텐데 어떻게 가능할까 예를 들어 생각하면 생각보다 간단한 문제다 5! = 5*4*3*2*1인데 $2^{k}$로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까 만약 k = 0이면 당연히 5!은 ..

• format_list_bulleted 정수론
• · 2023. 6. 24.
• textsms

팩토리얼 끝에서 가장 먼저 나오는 0이 아닌 수를 찾는 방법

1. 문제1 2553번: 마지막 팩토리얼 수 (acmicpc.net) 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net 2. 풀이 저번에 풀었던 문제와는 다르게 팩토리얼 계산한 값에서 마지막에서 0이 아닌 처음으로 다른 수가 나올때, 그 수를 출력하는 문제 쉽게 생각할 수 있는 방법은..? 저번에 배운 마지막에 0이 나오는 개수를 구하는 방법을 응용하기 마지막에 나오는 0의 개수 k를 구하고, n!을 계산하여 prod라고 저장한 다음에... prod를 $10^{k}$로 나눠준다면? 일의 자리가 정답이 된다 일의 자리는 어떻게 구해? str()로 바꿔서 -1번을 뽑아? 아니 str()로 바꾸는게 생각보다 시간 많이 먹어 ..

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

팩토리얼 끝의 0의 개수는 어떻게 셀 수 있는가

1. 문제 1676번: 팩토리얼 0의 개수 (acmicpc.net) 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 끝에서 0의 개수는 어떻게 세야할까 1000000은 뒤에 0이 6개이기 때문에, $10^{6}$이라고 바로 안다. 이처럼 끝에서 0의 개수가 n개이면, $10^{n}$이라고 바로 알고 있다 다른 수를 예로 들어보면 376129000은 $376129*10^{3}$ 따라서 어떤 수에서 끝의 0의 개수는... 소인수 분해해서 10이 몇개나 있는지 계산하면 될 것이다. 여기서 10은 2와 5의 곱이므로, 소인수분해해서 2와 5의 개수가 몇개나 있는지 계산하면 될 것이다 from..

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

탐욕적으로 생각하기 연습 -팩토리얼 분해-

1. 문제 2057번: 팩토리얼 분해 (acmicpc.net) 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 주어진 정수가 여러개의 팩토리얼의 합으로 나뉠 수 있는지 검사하는 문제 2. 풀이1 실버 5인데 왤케 어렵냐... 그리디 알고리즘이 확실히 경험이 없긴한가봐 내 해법은 일단.. 어떤 정수 N을 팩토리얼로 분해한다고 하면... 당연히 팩토리얼 값은 N보다 작아야 할 것이다 그래서 N보다 작은 팩토리얼을 일단 모두 구해놓는다 from sys import stdin n = int(stdi..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 5.
• textsms