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과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데.....
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..
https://en.wikipedia.org/wiki/Vandermonde%27s_identity Vandermonde's identity - Wikipedia From Wikipedia, the free encyclopedia Mathematical theorem on convolved binomial coefficients In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients: ( m + n r ) = ∑ k = 0 r ( m k ) ( n en.wikipedia.org 1. Vandermonde's identity 음이 아닌 정수 m..
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. 비둘기집 원리(pigeonhole principle) "n+1개의 물건을 n개의 상자에 넣을때, 최소한 한 상자에는 적어도 2개 이상의 물건이 반드시 들어있다" n+1개의 물건과 n개의 상자가 있으며, 각 상자당 한개씩의 물건만 존재한다고 가정한다면, 최대 n개의 물건이 존재할 수 있는데, 물건의 숫자는 n+1개이므로 어느 상자에도 들어가지 못한 물건이 하나 남을 수밖에 없으므로 모순이다. 그러므로 각 상자당 한개씩의 물건만 들어가야한다는 가정은 성립할 수 없으며, 적어도 하나의 상자에는 2개 이상의 물건이 존재한다. 너무나도 당연한 이 사실에 "비둘기집 원리(pigeonhole principle)"이라는 거창한 이름이 붙은 이유는 생각보다 많은 수학적 원리를 증명하기 위해 비둘기집 원리가 사용되며..
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!은 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
