1629:乗算

1848 ワード
白駿 パイ テキストリンク

質問する



コード#コード#

import sys
input = sys.stdin.readline

a,b,c = map(int,input().split())

def divCon(a,b):
    if b==1:
        return a%c 
    else:
        div = divCon(a,b//2)

        if b%2==0: #짝수 
            return div*div%c 
        else : #홀수 
            return div*div*a%c 

print(divCon(a,b))

解説


後、.単純に平方を計算し、残りの演算を行うだけでは余分な時間がかかります.
この問題のために理解しなければならない概念は私から見れば2つあります!

最初のコンセプト


平方の分割征服の概念を求めます

このように,繰り返しの二乗には対分計算の方法がある.
このようにすれば,盲目的に平方を求めるよりも時間の複雑さを大幅に減らすことができる.
既存の二乗アルゴリズムの時間複雑度はO(n)であり,分割征服されたアルゴリズムはO(logn)であるため,速度がより速い!
これを実現するコードは以下のコードである.
def divCon(a,b):
    if b==1:
        return a%c 
    else:
        div = divCon(a,b//2)
    if b%2==0: #짝수 
        return div*div%c 
    else : #홀수 
        return div*div*a%c 

그런데... 왜 return 할때마다 나머지 연산자를 해주니 의아할 수 있다.
그 이유는 바로 다음 개념에 있다.
### 나머지 연산자의 분배법칙
> ![](https://media.vlpt.us/images/seochan99/post/591713a0-5bff-41f2-a529-2f8d53d0c60a/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202021-10-03%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%205.19.27.png)
이런 방식으로 각각 나머지 연산을 해주고 마지막에 한번 더 해줘야한다..
몰랐다... 인생 23년 살면서 나머지 연산자의 분배법칙을 이제야 알았다니 대박..
그런데..! 이런 나머지 연산자의 분배법칙이 적용되지 않는 특이케이스가 있다.
바로 나눗셈에 대한 나머지 연산은 분배법칙이 적용되지 않기에 이를 위해서는 페르마의 소정리를 이용해서 분모를 분자로 올려야한다.
이에 대한 설명은 추후에 문제에 나오면 설명하겠다.

# 덧붙여서
> 문제의 난이도가 올라갈수록 배울 수 있는 부분이 점점 많아지고 몰랐던 부분도 점점 많아져 빈틈을 찾는거 같아 기분이 좋다..
물론... 하나하나 푸는데 주옥같지만말이닷...! 아직 실버1인데 큰일났당..케케
学院55日目-CSS
Javaマルチスレッド(4)のスレッド閉鎖