[백준] GCD 곱
문제 : https://www.acmicpc.net/problem/14860 문제요약 : 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)을 구해라 조건 : 1. 1 ≤ N, M ≤ 15,000,000 해설 : i) Naive Solution 각각의 i(1 ≤ i ≤ N), j(1 ≤ j ≤ M)에 대해 GCD(i, j)를 구해 곱하면서 O(NM)으로 구할 수 있겠죠? -> 15000000^2이므로 너무 느립니다 ii) 조금더 빠르게 N=8, M=8이라 합시다. GCD(i,j)들 중에 2의 인수가 얼마 있는지 알아봅시다. 1..
