약수를 세는 것보다 배수를 세는 것이 더 쉽다(홀수인 약수의 합, 유일한 소인수의 개수를 구하는 방법)

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제 단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다. https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$ 라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_..

• format_list_bulleted 정수론
• · 2024. 4. 11.
• 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

오일러 phi 함수 재활 -xφ(x) = n을 만족하는 x의 최솟값 구하기-

1. 문제 19577번: 수학은 재밌어 (acmicpc.net) 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 2. 풀이 오일러 phi함수를 구하는 방법 n을 소인수분해해서 소인수를 이용해 구하는 방법이 $O(\sqrt{n})$으로 빠르다 https://deepdata.tistory.com/571 오일러의 phi 함수 직접 구현해보면서 개념 익히기 1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데.....

• format_list_bulleted 정수론
• · 2023. 7. 6.
• 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

1부터 n까지의 최소공배수를 빠르게 구하는 방법

1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..

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

약수의 합 아주 빠르게 찾기 - 더블 카운팅(배수를 이용해 약수를 찾기), smallest prime factor

1. 문제 17427번: 약수의 합 2 (acmicpc.net) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 풀이 문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제 시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지 약수의 합을 구하는 공식은... https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수..

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