시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB122495188079.351%

문제

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

변수의 타입에 대해 공부했다면 231-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과 같은 타입을 사용하면 우리는 -263 ~ 263-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개의 정수 ai (1 ≤ ai ≤ 2,147,483,647)가 한 줄로 주어진다. 

출력

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

예제 입력 1

1 10
9999

예제 출력 1

9

예제 입력 2

2 1000000007
2147483647 2147483647

예제 출력 2

850618742

예제 입력 3

10 9999
100 100 100 100 100 100 100 100 100 100

예제 출력 3

1

출처

University > 아주대학교 > 2018 Ajou Programming Contest > Practice A번

  • 문제를 만든 사람: Acka
  • 문제의 오타를 찾은 사람: jh05013
  • 잘못된 데이터를 찾은 사람: tncks0121