글 읽기 - 반례 좀 부탁드립니다.

kinssang 6년 전 0

다른 맞춘 분의 소스와 비교해서 값을 넣어보아도 똑같은데 12% 쯤에서 에러가 뜹니다.

1000000000000 1000001000000

607940

이 뜨고

1 1000001

607927이 뜹니다.

물론 예제는 당연히 뜨고요.

왜 WA가 뜨는지 잘 모르겠습니다.

소수를 구한 후 -> 소수의 제곱으로 min과 max를 포함한 구간을 조회하는 방법을 썼습니다.

#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
	bool IsPrime[100006] = { true, true, }, answer[1000001] = {};
	vector<int> primes;
	for (int i = 2; i <= 100005; i++)
	{
		if (!IsPrime[i])
		{
			for (long long j = (long long)i*i; j <= 100005LL; j += i) IsPrime[j] = true;
			primes.push_back(i);
		}
	}
	long long min, max;
	int len, count = 0;
	len = (int)primes.size();
	scanf("%lld%lld", &min, &max);
	for (int i = 0; i < len; i++)
	{
		if (max / ((long long)primes[i] * primes[i]) == 0) break;
		for (long long j = min /((long long)primes[i]*primes[i]); j <= max /((long long)primes[i] * primes[i]); j++)
		{
			if ((long long)primes[i] * primes[i] * j - min >= 0) answer[(long long)primes[i] *primes[i] * j - min] = true;
		}
	}
	for (int i = 0; i < max - min + 1; i++) count += 1 - answer[i];
	printf("%d\n", count);
	return 0;
}

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

문제

문제

출처

ICPC

반례 좀 부탁드립니다.

kinssang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말