글 읽기 - 틀왜맞 반례질문입니다

aza1200 4년 전 0

다음 코드는 틀린 코드입니다

근데 다음 코드에 즉 40번쨰줄을 주석처리하면 정답이 맞게 나오더라고요

저같은 경우는 vec 안에다가 max(End) 보다 작거나 같은제곱수를 다집어넣고

arr 같은 경우는 평행이동하여 에라토스테네스의 체를 적용하였습니다.

제가 40번쨰줄을 한이유는 시간을 줄이기 위해서이ㅓㄴ데

40번쨰줄의 기능은 기존에 확인할려던 제곱수가 이전에 나왔던 제곱수의 배수일경우 확인할 필요가 없어서 넘기기를 시행한 것이었습니다. 그러나 이게 틀렸다고 나오더라고요 왜 그런것일까요?

#include <iostream>
#include<vector>

#define ll long long

using namespace std;

ll Start, End;
vector<ll> vec;

ll arr[1000010];

//start 와 end 사이에 number 로 나누어떨어지는 최소자연수
ll find(ll start, ll end, ll number) {
	ll what = start % number;
	if (what == 0) return start;
	else {
		ll spare = number - what; //
		return start + spare;
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> Start >> End;

	ll ex = 2;
	while (ex*ex <= End) {
		vec.push_back(ex*ex);
		ex++;
	}
	//max 보다 작은 제곱수 집어넣다//

	ll vsize = vec.size();
	for (ll i = 0; i < vsize; i++) {
		ll now = vec[i];
		ll ex = find(Start, End, now);
		if (ex > End) continue;
		if (arr[ex - Start]) continue; //이거 반례
		else {
			while (ex <= End) {
				arr[ex - Start] = 1;
				//cout << ex - Start << " \n";
				ex += now;
			}
		}
		//Start 부터 end 사이수중에 now로 나누어떨어지는 가장작은수?
	}



	int cnt = 0;
	for (ll i = 0; i <= End - Start; i++) {
		if (!arr[i]) {
			cnt++;
			//cout << i + Start << " ";
		}
	}
	//cout << "\n";

	cout << cnt << "\n";
}
/*
100000000 100000003
*/

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

문제

문제

출처

ICPC

틀왜맞 반례질문입니다

aza1200 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말