글 읽기 - python 나머지의 연산처리 질문입니다

fblood53 2년 전 1

처음에 시간초과의 코드를 제출하고 혹시나 해서 위에로 바꾸어 제출했더니 통과가 되었습니다..하지만 재귀를 돌면서 k값이 업데이트 될 때 k = k*k%z 가 될텐데 그러면 100 = 10 * 10 형태가 아니라 k = 10%12*10%12 가 되고 그 이후도 이런 연산이 되지 않나요? 그런데 어떻게 한번에 제곱값을 구한 후 나머지를 구하는 것과 값이 같게 나오는 지 이해가 잘 가지 않습니다..

#통과 코드
def speed_pow(x, y, z):
    if y == 1:
        return x%z
    else:
        k = speed_pow(x, y//2, z)
        if y % 2 == 0:
            return k*k%z
        else:
            return k*k*x%z


A, B, C = map(int, input().split())
print(speed_pow(A, B, C))

#시간 초과
def speed_pow(x, y):
    if y == 1:
        return x
    else:
        k = speed_pow(x, y//2)
        if y % 2 == 0:
            return k*k
        else:
            return k*k*x


A, B, C = map(int, input().split())
print(speed_pow(A, B) % C)

djm03178 2년 전 1

모듈로의 성질에 대해 알아보세요.매우 수학적인 개념입니다.

fblood53 2년 전 0

알아보던 중 잘 모르겠는 부분이 있어 질문드립니다.

A = C * Q1 + R1 이때 0 ≤ R1 < C 이고 Q1는 정수이다. A mod C = R1

B = C * Q2 + R2 이때 0 ≤ R2 < C이고 Q2 는 정수이다. B mod C = R2

LHS = (A * B) mod C

LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

mod C로 정리하면 C의 배수를 없앨 수 있습니다.

이 부분에서

LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C 이곳을 mod C로 정리한다는 것이 어떻게 정리가 되는 지 잘 모르겠습니다.

바쁜 시간 내주셔서 감사합니다

djm03178 2년 전 0

C mod C는 0이기 때문에 C가 곱해진 항은 모두 지워도 됩니다.

fblood53 2년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 나머지의 연산처리 질문입니다

fblood53 2년 전 1

djm03178 2년 전 1

fblood53 2년 전 0

djm03178 2년 전 0

fblood53 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말