글 읽기 - 범위를 넘어가는 것에 대한 질문

his130 6년 전 0

코드를 아래와 같이 짰습니다.

근데 calc 함수와 temp를 int형이 아닌 long long 으로 하면 정답이 됩니다.

근데 제 생각에는 return 할때

모든 변수를 각각 %C 해주기 때문에 return 값으로는 항상 int형 변수가 넘어가는 것 아닌가요?

예를 들어

return ((temp%C)*(temp%C))%C;

에서 결과값은 int 형이지 않나요? C가 int형 변수이기 때문에..

중간 계산 과정에서 (temp%C)*(temp%C) 이게 int 형을 넘을 수 있기 때문에 틀리게 되는건가요?

그래서 궁금한 점은 return 될때 저 값을 담는 변수가 없는데 , 이 때 결과값이 중요한것인지, 결과 과정이 중요한 것인지 알고 싶습니다.

#include<iostream>

using namespace std;

int A, B, C;
int calc(int a, int b)
{
	if (b == 0)
	{
		return 1;
	}
	else if (b % 2 == 0)
	{
		int temp = calc(a, b / 2);
		return ((temp%C)*(temp%C))%C;
	}
	else
	{
		return ((a%C)*(calc(a, b-1)%C))%C;
	}
}


int main()
{
	
	cin >> A >> B >> C;
	cout << calc(A%C, B) % C << endl;
	

	return 0;
}

djm03178 6년 전 1

결과 뿐만이 아니라 계산의 중간 과정 하나 하나에도 모두 자료형이 있습니다. 이 경우, 두 수를 곱하는 연산의 결과에서 이미 오버플로가 발생하기 때문에 그 후에 뒤늦게 나머지를 적용해도 소용이 없습니다.

his130 6년 전 0

음 그렇군요

그렇다면 (temp%C)*(temp%C) 같이 중간값들은 어떤 자료형을 따라가게 되나요?

djm03178 6년 전 0

이항 산술 연산자의 경우 둘 중 표현 범위가 큰 쪽으로 형변환 후 연산되고, 그 결과도 그 자료형이 됩니다. 둘 다 int라면 temp % C도 int니 둘을 곱해도 int죠. 둘 중 하나가 long long이라면 temp % C도 long long이고 곱한 결과도 long long입니다.

his130 6년 전 0

아 그렇게 되는군요... 감사합니다! 큰 도움이 됐습니다.

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

문제

문제

출처

ICPC

범위를 넘어가는 것에 대한 질문

his130 6년 전 0

djm03178 6년 전 1

his130 6년 전 0

djm03178 6년 전 0

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말