태영이의 코딩스토리

https://www.acmicpc.net/problem/10830 문제 풀이행렬을 제곱하기 위해서 B번 곱하면 시간 초과 분할 정복하여 log_B으로 제곱 연산 수행 (B번 -> log_B번으로 축소 가능)최종 시간 복잡도 O(N^3 logB) import java.util.*;public class Main { static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); long B = sc.nextLong(); long[][] matrix = new long[N][N]; for (int i =..

에라토스테네스의 체 에라토스테네스의 체수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.www.google.com 자바 코드// maxV는 최댓값boolean[] isPrime = new boolean[maxV + 1];Arrays.fill(isPrime, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i * i i * i가 maxV보다 작거나 같은 값까지 실행하는 이유는? 만약 n보다 작은 어떤 수 m이 m=ab라면 a와 b 중 적어도 하나는 루트n 이하이다. 즉, n보다 작은 합성수 m은 루트n​보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트 n​ 이하의 수의 배수만 ..