7087 : 나머지 연산 법칙
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
모듈러 산술(Modular Arithmetic)의 덧셈, 뺄셈, 곱셈, 거듭제곱 법칙을 확인하는 프로그램을 작성하십시오.
다음 연산들에 대해
- 덧셈(
- 뺄셈(
- 곱셈(
- 거듭제곱(
[제약 조건]
• 피연산자 $a, b$: $1 \le a, b \le 10^{18}$
• 모듈러 $m$: $1 \le m \le 10^9$
다음 연산들에 대해
(a op b) % m 의 결과를 계산하십시오.- 덧셈(
+): (a + b) % m- 뺄셈(
-): (a - b) % m (결과는 항상 0 이상 m-1 이하의 정수여야 함)- 곱셈(
*): (a * b) % m- 거듭제곱(
pow): (a^b) % m[제약 조건]
• 피연산자 $a, b$: $1 \le a, b \le 10^{18}$
• 모듈러 $m$: $1 \le m \le 10^9$
입력 설명
첫째 줄에 op a b m 형식의 명령이 주어집니다. op는 +, -, *, pow 중 하나이며, $a, b$는 $1$ 이상 $10^9$ 이하, $m$은 $2$ 이상 $10^9$ 이하의 자연수입니다.
출력 설명
계산 결과를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
+ 10 20 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
뺄셈 연산 후 음수가 나오면 법 m을 더해 0 이상의 수로 보정해 주어야 합니다.
거듭제곱 연산 시 b가 매우 크므로 단순 반복문 대신 분할 정복을 이용한 거듭제곱(Modular Exponentiation) 알고리즘을 사용하십시오.
거듭제곱 연산 시 b가 매우 크므로 단순 반복문 대신 분할 정복을 이용한 거듭제곱(Modular Exponentiation) 알고리즘을 사용하십시오.