백준 1629 곱셈

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

57825

15438

11352

25.950%

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

 

코드 설명: 정~말 간단해 보이지만, 생각보다 너무 잘 접근이 되지 않았던 문제이다. 

두가지 아이디어가 필요하다. 

예제 기준 

1) 1번 아이디어 

t = 10 

n = 11

s = 12 라 할 때, 

t * t * t * t * t  ... % s 가 

t % 12 * t % 12 ... 규칙은 진작 발견했고, 

 

https://st-lab.tistory.com/19#%EB%AA%A8%EB%93%88%EB%9F%AC

[백준] 10430 번 : 나머지 - JAVA [자바]

 

 

2) 2번 아이디어

10^30

 

$\rightarrow$ (10^15)^2

 

$\rightarrow$  (10^7)^2 * 10 * (10^7)^2 * 10

 

$\rightarrow$  (10^3)^2 * 10 * (10^3)^2 * 10) * (10^3)^2 * 10 * (10^3)^2 * 10) * 10

 

첫번째 아이디어는 그냥 규칙을 발견했었고, 

두번째 아이디어는 시간 단축을 위해 낸 아이디어다. 

 

첫번째 아이디어의 용례도 이해 못했고, 구현도 어려웠다. 

 

 

 

풀이 법은 생각보다 간단하다. 

 

Divide and Conquer 를 못해서 해매는 사람이 없길 바란다. 

 

반복되는 규칙을 나누자. 

 

temp = calculate(t, n//2)

 

 

 나눴으면 나누기를 멈추는 조건을 생성하자. 

 

n == 1: t 

 

즉 위 과정을 구현하면 

 

def calculate(t, n):

   if n == 1: t 

      temp = caluculate(t, n//2) # 나눈 값을 받아온다. 다만, terminate 조건이 잘 들어가 있어야 한다. 

   if n % 2 == 0:

      return temp * temp 

   else:

       return temp * temp * t 

 

다만 위에 방법으로는 시간초과가 난다. (이 정도 해줬으면 해결 되야 하는거 아닌가?)

사실은 시간 초과가 아니라 

 

1번의 해결방법으론 long long 자료형을 사용하는 것입니다.

그러나 이러한 자료형을 사용하더라도 문제는 제곱수이기 때문에 적은 연산에도 숫자가 기하급수적으로 커지게 되고 결과적으로 long long자료형의 범위도 넘어가버리게 됩니다.

따라서 연산을 할때마다 C로 나눈 나머지로 값을 바꿔주어야 자료형의 범위를 넘지 않고 계산이 가능합니다.

 

인터넷 글에 따르면 라고 한다. 

하긴, 제곱수면 커지는게 당연한데. 

이에 따라 매번 % 로 나눠준다. 

발견한 규칙이 유의미 해서 신기하다. 

 

실버 1이라 가볍게 보고 덤볐다가 눈물 쏙 뺐다. 

 

 

import sys
from tempfile import tempdir 
input = sys.stdin.readline

t, n, s = map(int, input().split())

def cal(t, n):
    if n == 1:
        return t % s
    temp = cal(t, n//2)
    if n % 2 == 0:
        return temp * temp  % s
    else:  
        return temp * temp * t % s

print(cal(t,n))