팩토리얼 끝의 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. 문제 11815번: 짝수? 홀수? (acmicpc.net) 11815번: 짝수? 홀수? B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. www.acmicpc.net 2. 풀이 소인수분해 해서 (지수+1)의 곱의 합으로 짝수인지 홀수인지 판단해볼라했는데 수가 10의 18제곱까지 있어서 그런지 시간초과 from sys import stdin n = int(stdin.readline()) num_list = list(map(int,stdin.readline().split())) for i in num_list: p = 2 answer..

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

탐욕적으로 생각하기 연습 -소인수분해 말고 인수분해하기-

1. 문제 2777번: 숫자 놀이 (acmicpc.net) 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 7: print(-1) continue else: prime[n] += 1 a,b = divmod(prime[2],3) if b == 2: b = 1 elif a == 2 and b == 0: a = 1 c,d = divmod(prime[3],2) answer = a+b+c+d+prime[5]+prime[7] print(answer) 2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고 3의 경우 2번 곱한 9까지 압축시켜야하고 5,7은 그대로 두면 되고 근데 또 압축이 가능한 경우가 2*..

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

소인수분해 심화응용 - linear sieve와 smallest prime factor 알고리즘 익히기

1. 문제 16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 500만 이내의 값에 대한 100만개의 수가 주어질때 각각을 소인수분해하는 문제 2. smallest prime factor smallest prime factor 알고리즘은 어떤 수의 가장 작은 소인수를 찾아 배열에 저장하는 알고리즘이다. 소인수분해를 수행하는 기본 알고리즘은.. p = 2부터 시작해서 $\sqrt{n}$까지 나눠보면서 소인수를 찾는데 #trivial prime factorizatio..

• format_list_bulleted 정수론
• · 2023. 1. 2.
• textsms

약수의 합과 약수의 개수 공식 익히기

1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$ 라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$ n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다. 1-1) 간단한 증명 왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다. 따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0..

• format_list_bulleted 정수론
• · 2022. 12. 26.
• textsms

오일러의 phi 함수 직접 구현해보면서 개념 익히기

1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까 문제 풀면서 익히기로 하자 2. 구현 예시1 - 가장 간단한 구현 가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다. 그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다. 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고, def gcd(a,b): while b != 0: a,b = b,a%b return a 2부터 ..

• format_list_bulleted 정수론
• · 2022. 12. 13.
• textsms