글 읽기 - 오버플러우 정수 범위

juyoung0609 1년 전 0

일단 제 코드에서 반복문의 i가 long long이 되어야 하는 것은 알았습니다.

그런데 2,5의 지수를 담는 변수denominator_2, denominator_5, numerator_2, numerator_5가 long long이 되어야 하는 것은 이해하기 힘듭니다.

계산해보려고 했는데 너무 헷갈려서 질문 남깁니다.

직관적으로 지수가 21억을 초과하지 않을 것 같아 int 형으로 해서 통과하긴 했는데 다른 분들 코드를 보면 long long으로 하시기도 했고 21억을 초과하지 않는다는 보장 없이 단순히 직관으로 int형으로 결정한 것이라 증명을 하고싶습니다.

감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int n, m, denominator_2=0, denominator_5=0, numerator_2=0, numerator_5=0;
	scanf("%d%d", &n, &m);
	for (long long i = 2; i <= m; i *= 2) {//곱하고 나서 오버플로우가 발생하여 음수가 되면 조건문을 만족하게 됌
		denominator_2 += m / i;
	}
	for (long long i = 5; i <= m; i *= 5) {
		denominator_5 += m / i;
	}
	for (long long i = 2; i <= n-m; i *= 2) {
		denominator_2 += (n-m) / i;
	}
	for (long long i = 5; i <= n-m; i *= 5) {
		denominator_5 += (n-m) / i;
	}
	for (long long i = 2; i <= n; i *= 2) {
		numerator_2 += n / i;
	}
	for (long long i = 5; i <= n; i *= 5) {
		numerator_5 += n / i;
	}
	numerator_2 -= denominator_2, numerator_5 -= denominator_5;
	if (0 < (numerator_2 < numerator_5 ? numerator_2 : numerator_5)) {
		printf("%d", numerator_2 < numerator_5 ? numerator_2 : numerator_5);
	}
	else printf("%d", 0);
}

peydihalta 1년 전 0

m이 2,000,000,000 (20억), n이 20억인 경우

denominator_2 += 10억 + 2.5억 + ...

denominator_5 이하동문

m이 0, n이 20억인 경우

n-m 조건문에 의해

denominator_2 += 10억 + 2.5억 + ...

denominator_5 이하동문

numerator_2와 numerator_5도 범위를 벗어날 일은 없습니다

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

문제

문제

출처

ICPC

오버플러우 정수 범위

juyoung0609 1년 전 0

peydihalta 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말