728x90 반응형 알고리즘 최종 (단계별)12 수학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. 소인수분해와 팩토리얼_알고리즘 소인수 분해 문제 링크 https://www.acmicpc.net/problem/11653 문제 풀이 정수 N을 소수의 곱으로 분해 소수를 구하지 않고도 해결 가능 N을 나눌수 없을 때까지 나누기 소스 코드 #include #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vectorsoinsu; int n=0; cin >> n; for (int i = 2; i*i n; int ret = 0; for (int i = 5; i 2023. 7. 8. 소수 찾기 및 판별_심화 에라토스테네스의 체 2부터 N까지의 수를 써놓고 지워지지 않은 수중에 가장 작은 수를 찾음 그수를 지우고 소수로 저장 그리고 그 수의 배수를 모두 지움 지워지지 않은 수 중에서 가장 작은 수 는 2이고 2는 소수이고 2의 배수를 모두 지움 그리고 3의 배수를 지움 5의 배수를 지운다. 7의 배수를 지운다. 그리고 11배수를 지우려고 하는데 이미 다 지워져 있고, 2,3,5,7로 인해서 11 * 11은 121로 100이 넘어서 더이상 수행 할 필요 없음 그럼 남아있는 모든 수가 소수이다. 문제 풀이 문제 링크 https://www.acmicpc.net/problem/1929 소스코드 #include #include using namespace std; const int MAX = 1000000; bool .. 2023. 7. 5. 소수_알고리즘 기본편 소수 bool prime(int x){ if(x 2023. 7. 4. 이전 1 2 3 다음 728x90 반응형
