1. 문제 25025번: 다항식 계산 (acmicpc.net) 25025번: 다항식 계산 첫 번째 줄에 두 정수 $N$, $P$ ($0 ≤ N ≤ 10^6$, $1 ≤ P ≤ 10^3$, $P$는 소수)가 공백 하나로 구분되어 주어진다. 두 번째 줄에는 $N+1$개의 정수 $a_N$, $\cdots$, $a_1$, $a_0$ ($0 ≤ a_i ≤ 10^9$)가 공백 하나로 www.acmicpc.net 2. 풀이 결국에 구해야하는 값은 $a_{i}k^{i} mod P$이고 k와 P가 서로소이므로 페르마의 소정리를 이용할 수 있다. 그런데 1초안에 P개의 값을 계산해야하니 이거 쉽지 않다 계수는 최악의 경우 $10^{6}$개이고.. 매 함숫값마다 이들을 모두 순회해야하니.. $O(10^{9})$는 돌아야겠는..
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. 문제 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
