112224   5년 전

포함 배제 원리 구현해서 푸는 문제같아서 int 형 범위인지 부터 확인해보려고,

1000000000 15

 2 3 5 7 9 11 13 17 19 23 29 31 37 41 43 47

일 때 

ec= 1640369913(배제되어야 할 숫자의 갯수)가 최대값을 가진 이후로 858280559

갖게 되는걸 확인하였고 오버플로우가 나지 않을거라고 생각했습니다.

근데 int 만 long long으로 바꿔줘야 AC가 되네요 ㅠㅠㅠ



chogahui05   5년 전

Tip. long long 범위도 넘어갑니다.

질답글에 올린 거 같은데.. 들어오는 수 < 100이잖아요.

100 이하 소수들 꽤 많습니다.

문제에 들어온 소수들의 집합을 A라고 하면. A에 속해있는 서로 다른, 임의의 두 수 a,b를 뽑았을 때

gcd(a,b) = 1이 되게 만들 수 있어요.

어떻게 만드냐.

모두 소수로 채워버리면 됩니다.

100이하의 소수들 중에서, 큰 거 15개 뽑아서 곱해보세요. long long 넘어가나 안 넘어가나.

112224   5년 전

아아...

집합에 포함되는 원소의 갯수가 아니라 최소공배수가 넘어가게 되는 거였군요.

원소의 갯수를 최대로 하는 경우만 생각해서 큰 소수들을 안넣어봤었네요 ㅠㅠ 

답변 감사드립니다!

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