글 읽기 - 이건 맞은건데 왜 틀렸을까요?

gee308 5년 전 0

틀렸으니까 틀렸겠죠?

근데 도저히 이유를 모르겠어서 정답코드랑 출력비교만 1시간 넘게 해봤습니다

1시간 넘게 해본 모든 출력에 다 같은 결과값이 나왔습니다.

사실 코드 보기엔 너무 지저분 할것인데

Permutation 함수를 이상하게 짜놔서

sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());

이렇게 주먹구구로 해결했거든요 정답뜨면 고치려고..

근데 정답이 안뜨네요..?

어디가 문제일까요

#include <iostream>
#include <vector>
#include <algorithm>
#define Compute_prime 100000
using namespace std;

bool* PrimeArray;

void swap(vector< long long> &arr,int i, int j)
{
	int temp;
	if (i != j)
	{
		temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

void Permutation(vector< long long> &arr, vector< long long> &arr2,int n, int r, int depth) //Permutation(N,R,0); NcR
{
	int i;
	 long long mid_value=1;
	if (n == r)
	{
		for (i = 0; i<r; i++) {
			mid_value *= arr[i];
		}
		arr2.push_back(mid_value);
		return;
	}
	if (r == depth) {
		for (i = 0; i<r; i++) {
			mid_value *= arr[i];
		}
		arr2.push_back(mid_value);
	}

	for (i = depth; i<n; i++) {
		swap(arr,i, depth);
		Permutation(arr,arr2,n, r, depth + 1);
		swap(arr,i, depth);
	}
}


long long numberOfMultuples( long long A,  long long B,  long long n)
{
	if (n == 1)
		return B + 1 - A;
	else if (A%n == 0)
		return (B / n) - (A / n)+1;
	else
		return (B / n) - (A / n);
}

void Eratos(int n)
{
	if (n <= 1) return;


	for (int i = 2; (i*i) <= n; i++)
	{
		if (PrimeArray[i])
		{
			for (int j = i*i; j <= n; j += i) PrimeArray[j] = false;
		}
	}
}

void Factorization(vector< long long> &arr,  long long N)
{
	for (long long i = 2; i <= N; i++)
		if (i<Compute_prime && PrimeArray[i] && N%i == 0 )
		{
			arr.push_back(i);
			while(N%i==0) N /= i;
		}
		else if (i >= Compute_prime-2)
		{
			arr.push_back(N);
			break;
		}
}

int main()
{
	int T;

	scanf("%d", &T);

	PrimeArray = new bool[Compute_prime+1];
	Eratos(Compute_prime);
	
	for (int j = 0; j<T; j++)
	{
		 long long A, B, N, sum = 0;
		cin >> A >> B >> N;

		vector< long long> arr;

		Factorization(arr, N);
		
		sum = B + 1 - A;
		for (int i = 1; i <= arr.size(); i++) //i가 1일때는 arr.size() C 1
		{
			vector< long long> arr2;
			Permutation(arr, arr2, arr.size(), i, 0);
			sort(arr2.begin(), arr2.end());
			arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
			if (i % 2 == 1) // -차례
			{		
				for (int j = 0; j < arr2.size(); j++)
					sum -= numberOfMultuples(A, B, arr2[j]);

			}
			else // +차례
			{
				for (int j = 0; j < arr2.size(); j++)
					sum += numberOfMultuples(A, B, arr2[j]);
			}
		}

		printf("Case #%d: %lld\n", j + 1, sum);
	}
}

ntopia 5년 전 1

https://ideone.com/pVw0LF

직접 돌려봤는데 예제도 안나오는데요...?

어딘가에 undefined behaviour 가 있어서

컴파일러마다 다른 결과를 뱉는 것 같습니다

gee308 5년 전 0

ntopia

당신은 갓인가요..??

새로운 검증법을 알려주셨네요

void Eratos(int n) 함수에 아래 코드를 추가하니 맞았네요...

for(int i=2; i<=n; i++) PrimeArray[i]=true;

이 코드를 빼도 제 컴파일러에서는 bool 동적할당과 동시에 모든값이 true가 됐었거든요...

감사합니다!

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

문제

문제

출처

ICPC

이건 맞은건데 왜 틀렸을까요?

gee308 5년 전 0

ntopia 5년 전 1

gee308 5년 전 0

ntopia

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말