[알고리즘] 수학

나머지 연산

---

• (A+B) mod M = ((A mod M) + (B mod M)) mod M
• (A*B) mod M = ((A mod M) * (B mod M)) mod M
• (A-B) mod M = ((A mod M) - (B mod M) +M) mod M (음수가 나올 수 있기 때문에)
• 나눗셈의 경우는 성립하지 않는다

 

최대 공약수(GCD)

---

• 유클리드 호제법(Euclidean algorithm)
• a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) == GCD(b, r)

//재귀함수 사용
int gcd(int a, int b){
    if( b == 0){
        return a;
    }
    else {
        return gcd(b, a%b);
    }
}

//재귀함수를 사용하지 않고
int gcd(int a, int b){
    while( b != 0 ){
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

//시간 복잡도 O(logN)

세 수의 최대공약수 → GCD(a, b, c) = GCD(GCD(a, b), c)

N개의 수의 최대공약수도 같은 방식으로 구할 수 있다.

 

최소공배수(LCM)

---

• A*B = GCD*LCM
• LCM = (A*B)/GCD

 

소수

---

어떤 수 N이 소수인지 아닌지 판별하는 방법

• N = A * B if A≤B, A≤√N B≥√N

bool prime(int n){
    if(n < 2){
        return false;
    }
    for(int i=2; i*i<=n; i++){
        if( n % i == 0) {
                return false;
        }
    }
    return true;
}

//시간 복잡도 O(√N)

N보다 작거나 같은 모든 자연수 중에서 소수 찾기 (에라토스테네스의 체)

• 2부터 N까지 모든 수를 써놓는다.
• 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
• 그 수는 소수이다.
• 이제 그 수의 배수를 모두 지운다.

어떤 수의 제곱보다 작은 수는 다 지워져 있다 → 11^2 = 121, 100이 넘어서 확인할 필요 x

 

vector<bool> arr(n+1);
arr[1] = true;

for(int i = 2; i <= sqrt(n); i++){
    for(int j = 2*i; j <= n; j += i)
        arr[j] = true;
}

• 골다바흐의 추측: 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다→ 에라토스테네스의 체를 활용하여 풀기 가능(but 아직 증명되지 않은 문제)
• 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다

 

팩토리얼

---

• 팩토리얼의 0의 개수 → 2와 5의 개수만 세주면 됨 → 5의 개수가 2의 개수보다 작으므로 5의 개수를 세어주면 된다
• N! 의 0의 개수 = [N/5] + [N/\(5^2\)] + [N/\(5^3\)] + ...
• 조합의 0의 개수 \({n}C{k} \)=\({n!}/{k!\cdot (n-k)!}\) 활용 → 2의 개수가 5의 개수보다 많다는 보장이 없으므로 둘 다 세어서 최소값을 구해주면됨