페르마소정리1

• 

  백준 1629 java - 곱셈(분할정복) 해당 문제는 쉽게 보면 쉽고 어렵게 보면 어려운 문제이다. 모듈러 연산을 활용한 것이기 때문에 모듈러의 특징을 잘 알아야 한다. 해당 문제에 대해서 두 가지의 풀이법으로 풀어보았으니 참고하시라! 1. 거듭제곱의 지수는 합연산이다. ex1) x^7 = x^(1+3+3) -> x^(1+(1+1+1)+(1+1+1)) ex2) x^4 = x^(2+2) -> x^((1+1) + (1+1)); 2. 지수가 0일 때 1이며, 1일 때는 자기자신 이다. 3. 결국 f(x) x는 지수 x = 1일 때 x; x = 0일 때 1; x가 홀수 일 때 x * (x/2) *(x/2) x가 짝수 일 때 (x/2)*(x/2) 라는 점화식이 도출된다. 4. 모듈러 연산이란 합, 차, 곱연산에 대해서 (A 연산 B) mod C ==(동.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 21.