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. 문제 14860번: GCD 곱 (acmicpc.net) 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 N*M 테이블에서 최대공약수를 구해본다. 예를 들어 N = 10, M = 10이라고 한다면.. 1은 곱해봤자 의미없으니까 2부터 테이블에 몇개나 나타나는지 한번 찾아보면 5*5 = 25개 있다는 것을 알 수 있는데 이는 행과 열에서 2의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..
1. 밀러 라빈 소수 판별법(Miller-Rabin primality test) 어떤 홀수 n이 소수인지 확률적으로 판별해주는 알고리즘 확률적이라는 말은, 합성수를 소수로 잘못 판별할 수 있다는 뜻이다. 주어진 n이 "합성수이다" 또는 "아마도 소수일 것이다"라는 대답을 내놓는다는 의미 2. 핵심 아이디어 알고리즘의 아이디어는 페르마의 소정리에서 시작한다. https://deepdata.tistory.com/573 페르마의 소정리 문제 풀어보면서 익히기 1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이..
1. 에라토스테네스의 체 기본형태 n이하의 소수를 구하는 알고리즘 n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면 소수만 남는다는 알고리즘이다 n = int(input()) result = [1]*(n+1) for i in range(2,int((n+1)**(1/2))+1): if result[i] == 1: for j in range(i*i,n+1,i): result[j] = 0 prime_list = [i for i in range(2,n+1) if result[i] == 1] 여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다. 왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다. 2. 에라토스테..
두 자연수 a,b를 입력받아 a/b를 소수점 20째자리까지 출력하라고 한다면 어떻게 해야할까? 일단 생각할 수 있는 방법은 %.20f 로 a/b를 출력하는 것이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a=sc.nextInt(); int b=sc.nextInt(); System.out.printf("%.20f",(double)a/b); } } 근데 이렇게 하면 정답이 아니다 왜 이런 문제가 발생하냐면 자바에서 float 타입은 소수점 아래 9째자리까지 표현할 수 있고 double 타입은 18째자리까지만 표현할 수 있다...
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
