글 읽기 - 여기서 오버플로우가 발생하지 않는 이유는 무엇인가요?

hellowfriend 1년 전 0

다음과 같이 코드를 짜면 오버플로우가 발생할 줄 알았는데 "맞았습니다."라고 뜹니다.

예를 들어서, A = 2,147,483,647, B = 3, C = (2,147,483,647 + 1) / 2 = 107374182일 때,

아래 코드에서

(pow(a, b-1) % C) * a

= (pow(2147483647, 2) % 107374182) * 2147483647

= ( (2147483647 % 107374182)*(2147483647 % 107374182) % 107374182) * 2147483647 //여기서 부터 우선수위대로 계산 시작

= ( (7*7)%107374182 ) * 2147483647

= 49 * 2147483647 이제 여기서 계산을 할 때 오버플로우가 발생해야 할 것 같은데 발생하지 않은 이유를 모르겠습니다.

아시는 분은 알려주시면 감사하겠습니다.

좋은 하루 되세요!

#include <iostream>
using namespace std;

long A, B, C;
long pow(long a, long b) {
 
    if (b == 1)    
    {
        return a;   
    }
    
    else if (b % 2 == 0)   
    {
        long half = pow(a, b / 2) % C;  
        return half * half;   
    }
    
    else 
    {
        return (pow(a, b - 1) % C) * (a);
    }
    
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> A >> B >> C;
    cout << pow(A, B) % C << "\n";
 
    return 0;
}

kokosoko59 1년 전 2

글쎄요 long이 64비트 데이터로 사용되어서 오버플로우가 안일어난거 아닐까요? 제가 알기로 long은 환경에 따라서 32비트 일수도 64비트 일수도 있기 때문에 만약 백준의 채점환경에서 long을 64비트 정수형으로 쓴다면 오버플로우가 안일어날것 같습니다.

아니면 단순히 그런 채점 데이터가 없는것일수도 있구요.

참고로 저는 위에서 말한 문제때문에 long을 사용하지 않고 int 아니면 long long 만 사용합니다.

hellowfriend 1년 전 0

오 신속하게 좋은 정보 알려주셔서 감사합니다!

adung7 1년 전 1

int로 바꾸니 틀렸다고 나옵니다.

위에분 말대로 long은 최소 4바이트를 보장하는것이지 4바이트가 아닙니다.

컴파일러에 따라 long은 8바이트가 될수 있기때문에 8바이트로 채점된것으로 보이네요.

hellowfriend 1년 전 0

아 제가 int의 범위와 long long의 범위를 잘 못알고 있었네요 ㅠㅠ.

죄송합니다. 저의 무지를 일깨우는데 도움을 주셔서 감사합니다.

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

문제

문제

출처

ICPC

여기서 오버플로우가 발생하지 않는 이유는 무엇인가요?

hellowfriend 1년 전 0

kokosoko59 1년 전 2

hellowfriend 1년 전 0

adung7 1년 전 1

hellowfriend 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말