README.md

[Bronze III] 오버플로우와 모듈러 - 15818

문제 링크

성능 요약

메모리: 113112 KB, 시간: 128 ms

분류

사칙연산, 수학

문제 설명

정수 오버플로우(Integer Overflow)란 정수형 변수가 연산 중 표현 범위를 넘어 의도와는 다른 값이 저장되는 현상을 말한다. C/C++, Java와 같이 변수의 타입과 함께 그 크기가 미리 정해지는 언어에서 종종 발생한다.

변수의 타입에 대해 공부했다면 2³¹-1, 2,147,483,647과 같은 수가 익숙할 텐데 이는 일반적인 4byte Integer 변수로 표현할 수 있는 양의 정수의 최댓값이다. 만약 4byte Integer 변수 1,000,000과 1,000,000을 곱하면 어떻게 될까? 결과는 컴파일러마다 다를 수 있지만, 우리가 원하는 값인 1,000,000,000,000이 나오지는 않을 것이다. 이미 연산과정에서 표현할 수 있는 범위를 벗어난 이 값은 4byte Integer가 표현 가능한 다른 값으로 변형되어 있을 것이다.

그렇다면 어떻게 할 수 있을까? 첫 번째는 보다 큰 범위의 정수 변수를 사용하는 것이다. 예를 들어 int가 아닌 C/C++에서의 long long, Java에서의 long과 같은 타입을 사용하면 우리는 -2⁶³ ~ 2⁶³-1 까지의 정수를 표현할 수 있다. 또한 놀랍게도 Python과 같이 타입에 따른 메모리 제한이 없어 사용자가 오버플로우에 대한 처리를 고려하지 않아도 되는 언어들도 있다.

이 문제에서 우리는 N개의 정수를 곱할 것이다. 하지만 정수의 곱이란 너무나도 빠르게 증가하기 때문에 그 결과가 정수변수로 표현할 수 있는 범위를 넘어갈 수도 있다. 그러니 우리는 (A × B) % M = ((A % M) × (B % M)) % M 과 같은 공식에 착안하여 N개의 정수를 곱한 결과값을 M으로 나눈 나머지를 비교하도록 하자.

N개의 정수와 M이 주어질 때, 모든 정수의 곱을 M으로 나눈 나머지를 계산하는 프로그램을 작성하시오.

입력

첫 줄에 연산될 정수의 개수 N(1 ≤ N ≤ 100)과 M(1 ≤ M ≤ 2,147,483,647)이 주어진다. 두 번째 줄에는 N개의 정수 a_i (1 ≤ a_i ≤ 2,147,483,647)가 한 줄로 주어진다.

출력

한 줄에 N개의 정수의 곱을 M으로 나눈 나머지를 출력한다.