Möbius Function

The Möbius function μ(n) is defined on positive integers with the following rules:

• μ(1) = 1
• For n > 1:
  • If n contains a squared prime facter (∃p: p² | n), then μ(n) = 0
  • Otherwise, if n has k distinct prime factors, then μ(n) = (-1)^k

This function satisfies a crucial identity:

$$\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1 \ 0 & n > 1 \end{cases}$$

Möbius Inversion

Given two arithmetic functions f and g where:

$$g(x) = \sum_{d \mid x} f(d)$$

The inverse relationship expresses f in terms of g:

$$f(x) = \sum_{d \mid x} \mu(d) \cdot g\left(\frac{x}{d}\right)$$

An equivalent formulation:

$$f(x) = \sum_{d \mid x} \mu\left(\frac{x}{d}\right) \cdot g(d)$$

Proof of the Inversion Formula

Starting from the right-hand side of the target equation:

$$\sum_{d \mid n} \mu(d) \cdot g\left(\frac{n}{d}\right) = \sum_{d \mid n} \mu(d) \sum_{e \mid \frac{n}{d}} f(e)$$

Rearranging the summation order:

$$= \sum_{e \mid n} f(e) \sum_{d \mid \frac{n}{e}} \mu(d)$$

Applying the summation property of μ:

• When n/e = 1 (i.e., n = e), the inner sum equals 1
• When n/e > 1, the inner sum equals 0

Therefore, only the term where e = n survives:

$$= f(n) \cdot 1 = f(n)$$

Application: Counting Pairs with Given GCD

Problem: Count ordered pairs (x, y) where 1 ≤ x ≤ a, 1 ≤ y ≤ b, and gcd(x, y) = d.

The answer is:

$$\sum_{x=1}^{a} \sum_{y=1}^{b} [\gcd(x,y) = d]$$

Since gcd(x, y) = d implies d | x, d | y, and gcd(x/d, y/d) = 1, we transform the problem by setting:

$$a' = \left\lfloor \frac{a}{d} \right\rfloor, \quad b' = \left\lfloor \frac{b}{d} \right\rfloor$$

Now we need:

$$\sum_{x=1}^{a'} \sum_{y=1}^{b'} [\gcd(x,y) = 1]$$

Transforming the Indicator Function

Using the property of μ:

$$[\gcd(x,y) = 1] = \sum_{k \mid \gcd(x,y)} \mu(k)$$

Substituting into the double sum:

$$\sum_{x=1}^{a'} \sum_{y=1}^{b'} \sum_{k \mid \gcd(x,y)} \mu(k)$$

By changing the order of summation and letting x = k·i, y = k·j:

$$\sum_{k=1}^{\min(a',b')} \mu(k) \cdot \left\lfloor \frac{a'}{k} \right\rfloor \cdot \left\lfloor \frac{b'}{k} \right\rfloer$$

Optimizing with Division Blocks

A naive O(n · min(a', b')) approach is too slow. Observing that ⌊a'/k⌋ values remain constant over intervals, we aply division block optimization to achieve O(√min(a', b')) per query.

Implementation

Linear sieve for computing μ values:

const int MAXN = 50000;
int primes[MAXN];
int mu[MAXN];
bool composite[MAXN];
int primeCount = 0;

mu[1] = 1;
for (int i = 2; i <= MAXN; ++i) {
    if (!composite[i]) {
        primes[primeCount++] = i;
        mu[i] = -1;
    }
    for (int j = 0; j < primeCount; ++j) {
        long long prod = 1LL * i * primes[j];
        if (prod > MAXN) break;
        composite[prod] = true;
        if (i % primes[j] == 0) {
            mu[prod] = 0;
            break;
        } else {
            mu[prod] = -mu[i];
        }
    }
}

Prefix sums for μ:

for (int i = 1; i <= MAXN; ++i) {
    prefixMu[i] = prefixMu[i-1] + mu[i];
}

Division block query:

long long solve(int A, int B) {
    long long result = 0;
    int upper = min(A, B);
    for (int left = 1, right; left <= upper; left = right + 1) {
        right = min(A / (A / left), B / (B / left));
        result += 1LL * (prefixMu[right] - prefixMu[left - 1]) 
                 * (A / left) * (B / left);
    }
    return result;
}

Main routine:

int main() {
    int a, b, d;
    scanf("%d %d %d", &a, &b, &d);
    printf("%lld\n", solve(a / d, b / d));
    return 0;
}