블로그 옮겼습니다

http://codeforces.com/contest/803/problem/D 너무 간단한 파라메트릭서치문제이다. 보자마자 파라메트릭서치임을 알았는데 구현이 막혀서 1시간동안 풀이못했기에반성하는 마음으로 기록용으로 글을 올린다..(정확히는 파라메트릭서치가 아니라 바이너리 서치라는데 나는 파라메트릭서치가 편하다..) 공백, 하이픈(-), 알파벳 대소문자로 이루어진 문자열 한줄과 만들 수 있는 최대 줄 수 K를 입력받는다.공백과 하이픈에서 줄을 바꿀 수가 있을 때 K줄을 넘지 않도록 하는 최대 가로폭(width) 를 구하는 문제이다.가로폭은 각 줄의 길이중 최대인 길이를 말한다. 그럼 그냥 단순히 가로폭의 상한을 정해놓고 그 가로폭을 최대로 갖도록 최대한 한줄에 꾸겨넣을 때 줄의 수를K개 이하로 만들 수 있..

큰 수 N의 모든 약수를 구하는 방법.큰 수라는 것은 int 의 범위를 넘으면서 long long 의 범위는 넘지않는 정도의 크기를 가진 수라고 생각하면 된다.약수를 구하는 가장 쉬운 방법은 1부터 N 까지 모두 돌며 N 을 나눈 나머지가 0인 것을 모두 찾으면 된다.하지만 N이 매우 크기 때문에 O(N) 으로는 구할 수가 없다. 그렇다면 어떻게 할까약수들의 특성중의 하나는 서로 짝을 이룬다는 것이다. 다시말해서N의 약수 i 가 있으면 N/i 도 약수라는 것이다. 그렇기 때문에 i가 N^0.5 를 넘어가면, 만약 약수가 존재하더라도 어차피 앞에서 봐준 것이기 때문에 또 봐줄 필요가 없다. 즉, N^0.5 까지만 반복하면서 N 을 나눈 나머지가 0인 수 i를 찾고i 를 찾았다면 N/i 도 같이 찾아주면 된..

http://codeforces.com/contest/803/problem/C N,K = K*(K+1)/2 냐 라는 말이 같고먼저 GCD를 정해주고 이 GCD로 strictly increasing 하는 K개로 분리가 가능한지즉, 고정된 GCD로 K개의 수를 각각 나눠서 모두 더한 값이 K*(K+1) 보다 크거나 같은지를 판단하기만하면되기 때문에GCD를 최대로 하기위해 가능한 가장 큰 GCD부터 가장 작은 GCD까지 반복하며 가장 큰 GCD를 찾은 뒤N을 그 GCD로 나눠서 strictly increasing 한 K개의 수를 만들고(1,2,3,... 처럼 1씩 증가시키다가 마지막 K번째 수에 다 때려박으면됨)K개의 수에 모두 GCD를 곱해주면 답이 될 것이다.만약 N/GCD >= K*(K+1)/2 가 되는..