문제에서 왜 항상 1e9+7로 나눈 나머지를 구하라고 할까?(모듈러 연산)

알고리즘을 풀다가 정답이 너무 클 수도 있으니 1000000007(1e9+7)로 나눈 나머지를 return 하라고 나왔다

왜 굳이 1e9+7를 return 하라는 걸까?

 

C/C++에서 수의 표현은 제한적이다

• int(4 bytes) : -2147483648(-2^31) ~ 2147483647(2^31-1) -> 근삿값 : 2e9
• long long(8 bytes) : -9.22337204e18(-2^63) ~ 9.22337204e18(2^63) -> 근삿값 : 9e18

21! 만 해도 long long 범위를 벗어남 -> 조합이나 가짓수를 세는 문제에서 쉽게 오버플로우가 난다!

큰 결과를 표현하는 데에는 많은 방법이 있지만, 굳이 변환을..?

문제 출제자는 큰 수를 표현하는 방법을 원하는 게 아니라 답을 도출해낼 수 있는지를 알고 싶기에, 모듈러 연산을 사용하는 것!!

 

그렇다면 왜 굳이 1e9+7일까!?

모듈러가 지나치게 작다면 비효율적으로 사용하는 것! -> 최대한 활용하기 위해서는 int의 max값에 가까워야 함

그럼 왜 int의 max값의 근삿값인 2e9를 사용하지 않을까?

 

덧셈 연산과 뺄셈 연산에서 2e9에 근사하는 값들의 연산을 한다면 2e9+2e9 = 4e9가 되어 오버플로우가 발생!

2^30에 근사하는 값을 가져야 함 -> 1e9에 가까운 값 중에 소수인 1e9+7을 사용하는 것

 

https://codeforces.com/blog/entry/19410

1000000007 considered harmful - Codeforces