[Jungol] 정올 1240 제곱근

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=523&sca=30

Approach

 

① low + high = 1 + 263- 1 = 263으로 long long 범위를 벗어나 Overflow 발생

    → unsigned long long 사용

 

② mid * mid = 262 * 262 = 2124 이기 때문에 unsigned long long으로도 처리할 수 없습니다.

이런 경우에는 mid <= target / mid로 처리할 수 있습니다.

(1 ≤ mid ≤ N 범위이기 때문에 0으로 나누는 오류는 없습니다.)

 

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

 

Code

#include <stdio.h>
typedef unsigned long long ULL;
ULL N;
 
ULL bsearch(ULL low, ULL high, ULL target) {
    ULL ans = target, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (mid <= target/mid) ans = mid, low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}
 
int main(){
    // freopen("input.txt", "r", stdin);
    scanf("%llu", &N);
    printf("%llu", bsearch(1, N, N));
}