수론은 정수의 성질을 연구하는 수학의 핵심 분야로, 특히 약수와 배수, 소수, 합동식 등에 관한 깊이 있는 분석을 포함한다. 본 문서에서는 수론에서 중요한 몇 가지 개념과 그 활용 방법을 다룬다.

곱셈 함수

정의역이 양의 정수 집합인 함수 ( f )가 임의의 서로소인 두 자연수 ( p, q )에 대해 ( f(pq) = f(p)f(q) )를 만족하면, 이 함수를 곱셈 함수(multiplicative function)라 한다. 만약 모든 자연수 ( p, q )에 대해 위 조건이 성립한다면, 이를 완전 곱셈 함수(completely multiplicative function)라 한다.

특히, 두 곱셈 함수의 곱은 다시 곱셈 함수임이 알려져 있다. 즉, ( f, g )가 곱셈 함수라면 ( h = f * g )도 곱셈 함수이다.

디리클레 콘볼루션 및 생성함수

디리클레 콘볼루션은 수론 함수 간의 기본 연산으로, 두 수론 함수 ( f ), ( g )에 대해 다음과 같이 정의된다:

[ (f * g)(n) = \sum_{d \mid n} f(d)g\left(\frac{n}{d}\right) ]

이 연산은 교환법칙, 결합법칙, 분배법칙을 모두 만족하며, 항등원 ( \varepsilon(n) )은 ( \varepsilon(1) = 1 ), ( \varepsilon(n) = 0 ) (for ( n > 1 ))인 함수이다. 또한, ( f(1) \neq 0 )인 경우, ( f )는 유일한 역원 ( g )를 가지며, 다음 점화식으로 계산할 수 있다:

[ g(n) = \frac{\varepsilon(n) - \sum_{\substack{d \mid n \ d < n}} f(d)g\left(\frac{n}{d}\right)}{f(1)} ]

또한, 두 곱셈 함수의 디리클레 콘볼루션은 곱셈 함수이며, 곱셈 함수의 역원 역시 곱셈 함수임이 증명 가능하다.

약수 분할 기법 (Divisor Block)

주어진 ( n )에 대해 ( \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor )의 값을 구할 때, ( \left\lfloor \frac{n}{i} \right\rfloor )의 값은 대략 ( 2\sqrt{n} )개의 서로 다른 값만 존재한다. 이를 이용해 같은 값을 가진 인덱스들을 묶어 처리할 수 있다.

각 블록 ( [l, r] )에서 ( \left\lfloor \frac{n}{i} \right\rfloor )의 값이 일정하므로, 해당 블록의 기여는 ( (r - l + 1) \times \left\lfloor \frac{n}{l} \right\rfloor )이다. 다음 블록의 시작은 ( r+1 ), 끝은 ( \left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor )로 결정된다.

ll solve(ll n) {
    ll ans = 0, l = 1, r;
    while (l <= n) {
        r = n / (n / l);
        ans += (r - l + 1) * (n / l);
        l = r + 1;
    }
    return ans;
}

모비우스 반전 공식

모비우스 함수 ( \mu(n) )는 다음과 같이 정의된다:

• ( \mu(1) = 1 )
• ( n )이 제곱 인자를 포함하면 ( \mu(n) = 0 )
• ( n )이 ( k )개의 서로 다른 소인수를 가질 때, ( \mu(n) = (-1)^k )

이 함수는 곱셈 함수이며, 선형 소수선을 통해 ( O(n) )에 계산 가능하다.

핵심 성질:

• ( \sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1 \ 0 & n > 1 \end{cases} )
• ( \sum_{d \mid n} \mu(d) = \varepsilon(n) ), 즉 ( \mu * \mathbf{1} = \varepsilon )

반전 공식: [ [\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d) ]

이 성질은 정수 쌍의 최대공약수가 1인지 여부를 판단하는 데 유용하게 사용된다.

실습 예제: ( \sum_{i=1}^n (k \bmod i) ) 계산

( k \bmod i = k - i \cdot \left\lfloor \frac{k}{i} \right\rfloor )이므로,

[ \sum_{i=1}^n (k \bmod i) = nk - \sum_{i=1}^n i \cdot \left\lfloor \frac{k}{i} \right\rfloor ]

여기서 ( \left\lfloor \frac{k}{i} \right\rfloor )의 값이 일정한 구간을 찾고, 각 구간 내에서 ( i )의 합은 등차수열 합으로 계산 가능하다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;

    ll ans = 0, l = 1, r;
    while (l <= n && k / l > 0) {
        r = min(n, k / (k / l));
        ans += (k / l) * (l + r) * (r - l + 1) / 2;
        l = r + 1;
    }

    cout << n * k - ans << '\n';
    return 0;
}

이러한 기법들은 알고리즘 경시대회에서 매우 자주 활용되며, 시간 복잡도를 ( O(\sqrt{n}) ) 또는 ( O(\sqrt{k}) )로 줄이는 데 필수적이다.