728x90 반응형 분활정복1 수학2_a^b에대해서 알아보자. a^b a의 b제곱을 빠르게 구해야함 int ans = 1; for (int i=1; i0){ if(b%2==1) ans*=a; a = a * a; b /=2; } return ans; } 이진수의 원리 왜? 이렇게 하지? 예를 들어 3의 27승인 경우 27은 이진수로 11011인데 2^0 + 2^1 + 2^2 + 2^3 + 2^4 인데 = 1 + 2 + 8 + 16 즉, 3^27 = 3^(1+2+8+16) 3^1 * 3^2 * 3^8 * 3^16 그렇기 때문에 a를 a*a로 곱해가면서 제곱을 구하게 됨 곱셈 문제 링크 https://www.acmicpc.net/problem/1629 문제 풀이 위의 내용을 적용하면된다. 소스코드 분할정복을 이용한 방법 #include using namespace std.. 2023. 7. 12. 이전 1 다음 728x90 반응형