문제https://www.acmicpc.net/problem/11693시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 역시 문제 날먹은 수학 이번 문제는 정수론 문제이다. 이 문제를 이해하기 위해서는 사전지식이 필요하다. 임의의 자연수 n에 대해 n이 다음과 같이 소인수분해된다고 해보자. 이때 n의 모든 약수의 합은 다음과 같이 나타낼 수 있다. 각 소인수에 대해 등비수열의 합을 구하고, 이 값들의 곱을 구하면 그것이 약수의 합이 된다. 해당 식을 전개하면 결국 n의 모든 약수들이 나오기 때문이다. 또한, 다음 성질이 성립한다는 것을 알 것이다. 이로 인해 n^m은 다음과 같이 나타낼 수 있다. 이제 이 모든걸 섞어보면 될 것이다. 결국 구해야하는 것은 다음 식이 된다. 각 항을 계..
문제https://www.acmicpc.net/problem/10830시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 빠른 행렬 거듭제곱 문제이다. 큰 틀에서는 두가지의 알고리즘이 들어간다. 분할 정복을 이용한 빠른 거듭제곱 알고리즘과 행렬곱 알고리즘이다. 분할정복을 이용한 빠른 거듭제곱 알고리즘은 전에 풀이했던 것이 있으니 다음을 참조하자. https://codejin.tistory.com/114 백준 1629번 C언어 풀이https://www.acmicpc.net/problem/1629 1629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.net 단순히 계속 곱했다가는..
https://www.acmicpc.net/problem/1629 1629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.net 단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까. 결국 이 문제의 핵심은숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다.O(n)으로 접근해서는 안된다.모듈러 연산은 https://codejin.tistory.com/68를 참조하자. 이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다. 그러면 오버플로우는 해결했고 이제..
