페르마의 소정리

문제간단한 정수론 문제이다. $$A^{B^C}, B^C / A$$ 결국 이 두개를 0.25초 안에 계산하면 되는 문제라고 볼 수 있다.첫번째의 경우에는 페르마의 소정리를 이용하면 간단하게 구할 수 있다. 페르마의 소정리는 아래과 같다. $$p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^p\equiv a\left({\rm mod}\ p\right) \text{이다.}$$ 이는 동치인 아래의 정리로 바꿀 수 있다. $$p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^{p-1}\equiv 1\left({\rm mod}\ p\right) \text{이다.}$$ 우리는 아래의 정리를 사용할 것이다. $  A^{7-1}\equiv 1\left({\rm mod}\ 7\righ..

cryptohack을 공부하면서 얻은 지식들을 정리하려고 한다.Greatest Common DIvisorGCD 즉 최대공약수에 대한 내용이다. 유클리드 호제법을 이용해서 두 정수의 최대공약수를 구하라고 한다. 이전에 유클리드 호제법을 다루었던 적이 있다.2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除nivr4y.tistory.comdef gcd(a, b): while b > 0: ..