TIL : 2024-09-13(금) :: C++ 오버플로우를 합동식(정수론)으로 해결하기

https://www.acmicpc.net/problem/15829

 

백준문제에 수식까지 다 알려주며 쉬운 문제를 하나 풀었는데 , 계속 정답체크가 안되서 찾아보았다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(void)
{
    //a == 1 -> 'a' - 96 
    //int hash = ch - 96;

    int r = 31;
    unsigned long long m = 1234567891;
    unsigned long long sum = 0;

    int StrSize;
    string str;
    cin >> StrSize >> str;
    
    int* num = new int[StrSize];
    for(int i =0; i < StrSize;i++)
    {
        num[i] = str[i] - 96;
    }

    for(int i =0; i < StrSize; i++)
    {
        sum += (num[i] * (unsigned long long)pow(r,i)) % m  ;
    }

    cout << sum % m ;
    delete[] num;
}

제공해준 수식에는 제곱이 있어 그저 cmath 라이브러리의 pow()함수를 사용해서 풀려고 했으나,

문제가 계속 풀리지 않았었다.

 

하지만 원인은 오버플로우였었다. Pow에 타입캐스팅으로 unsigned long long 자료형도 선언했지만 Pow에서 Return하는 자료형은 이미 double이기에 i의 숫자가 49승만 되도 결국 오버플로우 발생한다.

 

그럼 해당 숫자를 받을 자료형이 없는가? 그건 아니다

정수론의 합동식 성질을 이용하는것이다. 

* 합동식이란 ??

합동식 표현 방법 / 모듈러 연산이라고도 한다.

 

합동식의 정수배 성질을 이용하여 문제를 해결한다.

해당 성질이 적용 됨으로

위의 방식도 적용이 된다.

즉, 해당 문제도 정답도 숫자 m을 나눈 나머지값을 원한다. 

pow함수를 쓰는게 아닌 직접 Pow함수를 선언하여 만들고

제곱할때마다 숫자 m (123456791)를 나눠서 나머지값을 구하고 오버플로우 나지 않게 대처하는것이였다.

 

밑에 코드는 위에 설명을 반영하여 고쳐서 제출하였다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

unsigned long long Pow(int a , int b)
{
    unsigned long long result = 1;
    for(int i = 0; i < b ; i++)
    {
    	//합동식의 성질이 잘 드러나는 부분
        result *= a;
        result %= 1234567891;
    }

    return result;
}

int main(void)
{
    //a == 1 -> 'a' - 96 
    //int hash = ch - 96;

    int r = 31;
    unsigned long long m = 1234567891;
    unsigned long long sum = 0;

    int StrSize;
    string str;
    cin >> StrSize >> str;
    
    int* num = new int[StrSize];
    for(int i =0; i < StrSize;i++)
    {
        num[i] = str[i] - 96;
    }

    for(int i =0; i < StrSize; i++)
    {
        sum += (num[i] * Pow(r,i));
    }

    cout << sum % m ;
    delete[] num;
}

 

---

공부해야될것 :: 오늘 유니티 미니프로젝트 발표가 있어 발표를하고 다른조들 작품을 보며 필요한 점을 배웠었다.

파티클을 스크린 뷰에서 표현 하게 할 수 있는것 : UI 의 카메라 렌더링 모드를 바꾸기 (12조)
우리가 흔히 보는 광고창이 스르륵 넘어가는 것을 유니티 컴포넌트로 구현 : 스크롤뷰 컴포넌트 사용하기 ( 6조 )