글 읽기 - 이것 저것 테스트 해 봤는데 맞는거 같은데.. 원인을 모르겠네요.

graytiger 4년 전 0

sqart 대신 bst 라는 함수를 만들어서 min , max 제곱근을 찾습니다.

이것 저것 테스트 값을 넣어서 테스트 해보는데 어디가 잘 못 된 것인지 모르겠네요.

예를 들면 min = 3, max = 15면

min 에 대한 제곱근은 2, max 에 대한 제곱근은 9를 제외하는 방식으로 구현을 했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
typedef unsigned long u32;
typedef unsigned long long u64;

u64 bst(u32 s, u32 e, u64 target)
{
	u64 m;
	u64 upper;
	u64 lower;

	//	printf("%u %u\n", s, e);

	//if (target == 0) {
	//	return 0;
	//}

	if (s > e) {
		return 0;
	}

	m = ((u64)s + (u64)e) / 2;


	lower = (u64)(m - 1) * (u64)(m - 1);
	upper = (u64)m * (u64)m;

	if (lower> target) {
		return bst(s, m - 1, target);
	}
	else if (upper<target) {
		return bst(m + 1, e, target);
	}
	else if (upper > target && lower == target) {
		return (m-1);
	}
	else {
		return m;
	}
}

int main()
{
	u64 l;
	u64 r;
	u64 lresult;
	u64 rresult;
	u64 temp = ((u64)1024 * (u64)1024 * (u64)1024 * (u64)4) -1;
	u64 final_result;

	scanf("%lld lld", &l, &r);
	//l = 1;	r = 16;
	lresult = bst(0, (u32)temp, l);
	rresult = bst(0, (u32)temp, r);
	
	if ((rresult* rresult) > r) {
		rresult--; // last value
	}
	if (lresult == 1) {
		lresult++;
	}


	final_result = (r - l +1) -(rresult - lresult +1);
	if (l == 1) {
		final_result--;
	}

	printf("%lld\n", final_result);
	return 0;
}

nahwasa 4년 전 0

일단 올려주신 코드 자체로는

https://ideone.com/wGGoM2

기본 TC인 1, 10조차 ideone 기준 0이 뜹니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이것 저것 테스트 해 봤는데 맞는거 같은데.. 원인을 모르겠네요.

graytiger 4년 전 0

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말