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_..
1. 문제 9359번: 서로소 (acmicpc.net) 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 2. 풀이 $10^{15}$이내에서 $N = 10^{9}$과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다 심지어 쿼리로 주어지니 더 어렵다 먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다. N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 범위 내에서 N과 서로소인 수와 서로소가 아닌 수로..
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과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데.....
1. 문제 11692번: 시그마 함수 (acmicpc.net) 11692번: 시그마 함수 첫째 줄에 1 ≤ n ≤ m인 모든 n의 σ(n) 중에서 값이 짝수인 것의 개수를 출력한다. www.acmicpc.net 2. 약수의 합의 성질 - 언제 짝수이고 언제 홀수가 될 수 있는가? 정수 n의 모든 양의 약수의 합을 시그마 함수(sigma function)라고 부르는데 일반적인 정의로... $$\sigma_{z}(n) = \sum_{d | n} d^{z}$$ z = 1이면 모든 양의 약수의 합을 나타내고 z = 0이면 n의 약수의 개수를 나타낸다. 편의상 지금부터 서술하는 모든 시그마 함수는 z = 1인 경우이다. https://en.wikipedia.org/wiki/Divisor_function
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!은 ..
1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$를 이용하자. 그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$를 얻는다. 그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$ 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
