제곱승 구하기 (1) 썸네일형 리스트형 [백준 ]11401 이항계수 3 (JAVA) 일반적인 이항계수 공식으로는 시간초과및 오버플로우가 나와버린다. 그도 그럴것이 문제에서는 최악의 경우 4000000!을 계산하고 그래야하는데 이것은 long타입의 저장범위를 아득히 넘어버린다. 그로 인해 우리는 다른 방법을 생각해 보아야 하는데 여기서 나오는것이 페르마의 소정리이다. 우리는 알고리즘 문제를 푸는것이지 수학문제를 푸는것이 아니기 때문에 간략하게 정리만 하고 넘어갈것이다.모듈러연산(페르마의 소정리)의 공식에는 덧셈,뺄셈,곱셈이 있으면 나눗셈은 통용되지 않는다. 우선 페르마의 정의는 이렇다. 여기서 조금만 더 나아간다면 이렇게 유도가 가능할 것이다. 그렇다면 우리가 구하고 싶은 나눗셈 꼴은 역원으로 구할수있으면 이를 정리하면 위와 같이 나오며 최종적으로 우리가 도출하고자 하는 계산식은 아래와 .. 이전 1 다음
