나머지 연산
(A * B) % m = (A%m) * (B%m) % m ex) (7 * 8) % 5 = 56 % 5 = 1, (7%5) * (8%5) % 5 = 6 % 5 = 1
→ 오버플로우가 나올 수 있는 연산에서는 연산 전과 후에 매번 나머지 연산을 수행해주면 된다.
A < 0일 경우, A % m을 그냥 수행하면 나머지 값이 음수가 나온다.
따라서 양수의 나머지값을 얻기 위해 다음 코드를 추가하자.
while (A < 0) A += m;최대공약수 (Greatest Common Divisor)
최대공약수를 구하는 빠른 방법 : 유클리드 호제법
gcd(a, b) = gcd(b, r)임을 이용한다.
//반복문
int gcd(int a, int b) {
int r;
while (b) {
r = a % b;
a = b;
b = r;
}
return a;
}
//재귀함수
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }A와 B의 최대공약수와 최소공배수를 곱하면 A * B이므로, 최소공배수는 최대공약수를 가지고 구할 수 있다.
분할 제곱
일단 코드부터 보자.
//base^expon을 계산한다.
int fpow(int base, int expon) {
int result = 1;
while (expon > 0) {
if (expon % 2 == 1) {
result *= base;
}
base *= base;
expon /= 2;
}
return result;
}위의 기본형에서, 문제에서 요구사항이나 값의 범위에 따라 자료형을 long long으로 확장하거나 매 곱셈마다 나머지 연산을 추가하는 등의 변형을 가하면 된다.
원리는 거듭제곱을 이용한 것이다. 예시를 통해 이해해보자.
3^13을 구하려고 한다. 13을 2의 거듭제곱의 합의 꼴로 나타내보자. 이진수의 표현방식과 유사하다.
13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1
그렇다면 3^13은 3^8 * 3^4 * 3^1로 나타낼 수 있을 것이다.
다시 위의 코드를 보자. base는 3부터 시작해서 매 반복마다 3^2, 3^4, ...로 지수가 2의 거듭제곱이 된다.
그렇게 증가한 base는 현재의 지수가 13의 '2의 거듭제곱의 합'에 포함될 때만 연산에 사용된다. 위의 예시에서는 base가 3^1, 3^4, 3^8일 때만 result에 곱해질 것이다.
'2의 거듭제곱의 합에 포함될 때'를 구하는 방법은 십진수를 이진수로 변환할 때와 유사하다. 십진수를 2로 나누면서 나머지가 1일 때마다 합에 포함시키면 된다.
소수 판정
처음 프로그래밍을 연습할 때는 이중 반복문을 통해 일일히 확인했지만, 우리에게는 더 좋은 도구가 존재한다. 바로 '에라토스테네스의 체' 이다. (진짜 도구임)
이것도 원리보다는 코드를 먼저 보자.
vector<int> prime; //소수만 저장하는 배열
bool checked[n + 1]; //checked가 0일 경우 소수
void Eratosthenes(int n) {
for (int i = 2; i <= n; i++)
if (!checked[i]) {
prime.push_back(i);
for (int j = i * i; j <= n; j += i) checked[j] = 1;
}
}2부터 n까지의 소수를 구하고자 한다.
먼저 2는 소수니까 prime에 추가한다. 그리고 j에 대한 반복문에서 2의 배수를 모두 '소수 아님'으로 변경한다. 3은 소수니까 똑같이 진행된다. 4는 2의 반복문에서 '소수 아님'으로 판정되었으므로 바로 넘어간다. 5는 똑같이 진행, 6은 2에서 판정됐으니 생략, ... 이런식으로 수행하다보면 일반적인 이중반복문보다 더 빠르게 소수를 찾을 수 있다.
속도를 빠르게 해주는 요인은 i의 배수만 확인하는 것도 있고, j 반복문의 시작이 i*i인 것도 있다. 7의 배수를 확인한다고 생각해보자. j = 7부터 시작해도 되겠지만, 7*2, 7*3, 7*4, 7*5, 7*6까지는 이미 j가 2, 3, 5일 때 2*7, 3*7, 2*14, 5*7, 2*21로 확인되었으므로 굳이 다시 계산할 필요가 없다. 따라서 i * i부터 시작해도 결과가 같다.
에라토스테네스의 체는 편리하지만 두가지 위험이 존재한다.
1. j 반복문의 시작이 i*i이다
위에서는 장점이였지만, i가 10^5 만 넘어가도 i * i는 100억으로 int 자료형의 범위를 넘어간다. 따라서 오버플로우를 고려해 j를 long long으로 선언하는 것도 좋다.
2. 크기 n의 배열이 필요하다
메모리 절약을 위해 배열 자료형을 bool로 했지만, 1부터 1억까지의 소수를 찾아야한다면 여전히 1억 바이트의 메모리를 사용해야 한다. 그래서 일반적으로 PS에서는 작은 크기의 배열만으로도 해결할 수 있는 문제를 제시한다. 이런 문제에서 우리는 무작정 bool checked[MAX+1]로 배열을 선언할 것이 아니라, 배열의 크기를 최소화하는 방법을 고민해보아야 한다.