글 읽기 - 혹시 힌트좀 얻을 수 있을까요..?

simm4256 7년 전 1

도저히 풀이 방법이 떠오르질 않습니다.

1~k까지의 소수를 전부 구해보는것도 안되고

k+1~루트p까지는 최대범위가 10^50이니 더더욱 말이안되고..

문제에 나온 그림이 뭔가 힌트일거라 생각해서 제 나름대로 열심히 해석해보려 했으나

최대공약수가 나온다는건 알겠는데 나머진 이해가 하나도 안되네요 ㅠㅠ

myungwoo 7년 전 0

1 ~ K까지의 소수를 모두 구하는 방법이 왜 안되죠?

simm4256 7년 전 0

아아 멍청했네요 소스를 잘못 짰었나봐요

근데 이번엔 틀렸습니다가...

아무래도 double 자료형 특성때문에 틀린거같은데

big integer를 써야하나요?

#include <iostream>
#include <cmath>
using namespace std;

int arr[1000001] = { 0, }, k;
double p;

int main() {
	cin >> p >> k;
	int i, j;
	arr[1] = 1;
	for (i = 2; i <= k; i++) {
		if (arr[i] == 0) { //소수이면 arr[i]=0, 아니면 arr[i]=1
			if (floor(p/i)*i==p) {
				cout << "BAD " << i;
				return 0;
			}
			j = i;
			for (j = i + i; j <= k; j += i) //예니체트리 체
				arr[j] = 1;
		}
	}
	cout << "GOOD";
}

myungwoo 7년 전 17

double을 사용하면 당연히 안되죠. double은 부동소수점으로 실수를 표현합니다. 실제로 double 자료형의 표현 범위를 보면 꽤나 넓어보일 수 있지만 당연히 공간을 64비트밖에 안쓰므로 표현할 수 있는 유효숫자의 개수가 적다고 보면 돼요.

이 문제에서는 큰 수 K가 어떤 소수 p에 의해 나누어 떨어지는지만 확인하면 되므로 Big Integer 구현이 필요가 없습니다.

관련해서는 아래 코드를 보시죠.

int mod(char *S, int p)
{
	// S는 수를 문자열로 표현한 것, 1324 -> "1324"
	int ret = 0;
	for (int i=0;S[i];i++) ret = (ret*10 + (S[i]-'0')) % p;
	return ret;
}

simm4256 7년 전 1

감사합니다.

알려주신 mod 함수 진짜 꿀팁이네요.

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

문제

문제

출처

ICPC

혹시 힌트좀 얻을 수 있을까요..?

simm4256 7년 전 1

myungwoo 7년 전 0

simm4256 7년 전 0

myungwoo 7년 전 17

simm4256 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말