블로그 이사 중입니다 >> gumgood.github.io

C++11 x == M일 때, x = 0y == N일 때, y = 0으로 생각하면, 연도 year 은 다음을 만족한다 year = x (mod M)year = y (mod N) year = iM + x = jN + y (i, j : nonnegative integer) 이 때, 가 표현할 수 있는 년도는 gcd(x,y)이므로 최대 x*y년도를 표현할 수 있다. 따라서 i와 j의 범위는 다음과 같다 0

C++11 구현 연습

C++11

C++11 n!의 오른쪽 끝에 있는 0의 개수를 구하는 문제 n!의 소인수들로 10을 몇 개나 만들 수 있는지 묻는 것이다. 1~n 사이의 수들의 소인수 중에 2와 5가 몇 개인지 찾으면 그 중 작은 값이 10의 개수임을 알 수 있다. n의 범위는 10^9이므로 O(n)에는 돌릴 수 없다. '1~n의 소인수 중에 2와 5의 개수'를 쉽게 세는 방법이 있다. n까지의 수 중 2의 배수는 n/2+n까지의 수 중 4의 배수는 n/4+n까지의 수 중 8의 배수는 n/8+... 와 같이 count 하면 소인수에 2^k를 포함하는 수는 k번 세어지므로 O(log2(n))에 2의 개수를 구할 수 있다. 5의 개수 역시 같은 방법으로 O(log5(n))에 구할 수 있다. O(logn)

C++11 1~100 사이 완전 세제곱 수들을 표시해두고 가능한 모든 a,b,c에 대해 다음을 만족하는 d가 있는지 확인한다. a, b, c가 가질 수 있는 수는 각각 n이므로 O(n^3)

C++11 1/i!을 double 형으로 표현하고 덧셈하면 소숫점 오차가 생길 수도 있어서 분자와 분모를 따로 나눠서 계산하고 마지막에 나눗셈 연산을 하면 오차를 줄일 수 있다. 이 문제에서는 분모를 9!으로 통일해서 분자를 따로 덧셈했다.

C++11 각 가로수 사이의 간격이 모두 같아야 한다. 각 가로수 사이의 간격들의 greatest common divisor을 구해 가로수 사이의 간격으로 정하면 답을 쉽게 구할 수 있다. 가능한 최대 간격이 gcd이기 때문이다.

C++11 가능한 모든 공차에 대해 밟을 수 있는 타일의 합을 구해본다.