글 읽기 - 반례를 못찾겠어요... 3%에서 자꾸 틀리네요 ㅠ

qodlstjd12 3년 전 0

제가 시도해본 케이스들입니다.

A B OUTPUT

1 1^14 -> 670121개 (게시판 참고)

4 4 -> 1개 (4)

5 5 -> 0개 (x)

7 7 -> 0개 (x)

1 1000 -> 25개 (예제)

11 16 -> 1개 (16)

8 9 -> 2개 (8,9)

9 10 -> 1개 (9)

평범한 경우와 오버플로우가 발생할 수 있는 경우, 경계값에 "거의 소수"가 있는경우 등 모든 경우를 다 테스트해봤는데 3%에서 틀립니다.

도움주실분 계신가요 ㅠㅠ

#include <iostream>
#include <cmath>
using namespace std;
bool Prime[10000011];
int Real_Prime[10000011];

long long A, B, cnt;

void Eratos() {
	long long i, j;
	for (i = 2; i * i <= B; i++) {
		if (!Prime[i]) {
			Real_Prime[cnt++] = i;
			for (j = i * 2; j * j <= B; j += i)
				Prime[j] = true;
		}
	}
}
int Almost_Prime(int prime) {
	long long i;
	int answer = 0;

	for (i = prime; i * prime < A; i *= prime);

	for (; i <= B / prime; i *= prime, answer++);
	
	return answer;
}
int main()
{
	long long i, j;
	long long answer = 0;
	cin >> A >> B;
	Eratos();
	for (i = 0; i < cnt; i++)
		answer += Almost_Prime(Real_Prime[i]);

	cout << answer << endl;
}

thdruddyd21 3년 전 0

안녕하세요 해결하셨나요? 저도 같은 문제로 고통받고 있습니다

deviltina 2년 전 0

전 java로 했는데 3%에서 똑같이 틀리더라고요. 여러가지 고민하다가 간신히 풀었는데요.

조심스럽게 추측하기로는 overflow문제인 듯 싶습니다.

11, 14, 23 을 다시 한번 check해보심이 어떨까 하네요.

제가 드리는 반례는

10000000000000 100000000000000

제출 : 485869

정답 : 439554

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

문제

문제

출처

ICPC

반례를 못찾겠어요... 3%에서 자꾸 틀리네요 ㅠ

qodlstjd12 3년 전 0

thdruddyd21 3년 전 0

deviltina 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말