CF 1499D - The Number of Pairs

Rating: 2100
Tags: dp, math, number theory
Solve time: 5m 6s
Verified: yes

Solution

Problem Understanding

We are asked to count how many ordered pairs of positive integers $(a, b)$ satisfy a single arithmetic constraint that mixes their least common multiple and greatest common divisor. For each test case, three integers $c$, $d$, and $x$ are given, and we must count how many pairs produce exactly $c \cdot \mathrm{lcm}(a,b) - d \cdot \gcd(a,b) = x$.

The structure of the expression suggests that the key difficulty is not enumeration of pairs directly, but understanding how $\gcd$ and $\mathrm{lcm}$ interact. Since $\mathrm{lcm}(a,b)$ and $\gcd(a,b)$ are tightly coupled, any naive search over $a$ and $b$ up to large values is immediately infeasible. Even restricting both to $\sqrt{x}$ or similar bounds does not help because $\mathrm{lcm}$ can be large even for small gcd structure variations.

The constraints allow up to $10^4$ test cases with values up to $10^7$. A quadratic or even $O(n \sqrt{n})$ per test solution would fail. The only viable direction is to reduce the problem to something that depends on divisors of $x$ or a derived value per test case.

A key edge situation appears when $x$ is small or when $c \cdot \mathrm{lcm}(a,b)$ and $d \cdot \gcd(a,b)$ nearly cancel. For example, if $c = d$ and $x = 0$, the equation becomes $\mathrm{lcm}(a,b) = \gcd(a,b)$, which forces $a = b$. A naive solver that tries to manipulate ratios without enforcing integer constraints may incorrectly include non-integer combinations or miss this degeneracy entirely.

Another subtle case is when $a$ and $b$ are coprime. Then $\gcd(a,b) = 1$ and $\mathrm{lcm}(a,b) = ab$, so the equation becomes $c \cdot ab - d = x$, which heavily restricts feasible products. A direct factorization approach is required to avoid iterating over all pairs.

Approaches

A brute-force strategy would try all pairs $(a, b)$ up to some limit and compute $\gcd$ and $\mathrm{lcm}$ directly. This is correct but fundamentally infeasible. Even if we assume $a, b \le 10^7$, the search space is $10^{14}$, and even restricting to $x$-dependent bounds still leaves far too many candidates per test case.

The key observation is to separate the structure of $\gcd$ and $\mathrm{lcm}$. Let $g = \gcd(a,b)$, and write $a = g \cdot a'$, $b = g \cdot b'$ with $\gcd(a', b') = 1$. Then $\mathrm{lcm}(a,b) = g \cdot a' \cdot b'$. Substituting into the equation gives:

$$c \cdot g a' b' - d \cdot g = x$$

Factoring out $g$:

$$g (c a' b' - d) = x$$

This transforms the problem into a structured divisor enumeration problem. For each possible gcd value $g$ dividing $x$, we reduce the equation to:

$$c a' b' - d = \frac{x}{g}$$

$$c a' b' = \frac{x}{g} + d$$

Thus:

$$a' b' = \frac{\frac{x}{g} + d}{c}$$

This imposes two strict conditions. First, $(x/g + d)$ must be divisible by $c$. Second, once we define $k = (x/g + d)/c$, we must count the number of coprime factor pairs $(a', b')$ such that $a' b' = k$.

The second part is classical: if $a'$ and $b'$ are coprime and their product is $k$, then each prime factor of $k$ must go entirely to one side or the other. This implies the number of ordered coprime factor pairs is $2^{\omega(k)}$, where $\omega(k)$ is the number of distinct prime factors of $k$.

The problem reduces to iterating over divisors of $x$, performing a divisibility check, factoring a reduced number, and accumulating powers of two over prime signatures.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n^2)$ per test	$O(1)$	Too slow
Optimal	$O(\sum \sqrt{x} + \sqrt{k})$ per test (amortized fast factorization)	$O(1)$ extra	Accepted

Algorithm Walkthrough

Iterate over all divisors $g$ of $x$. This is necessary because $g$ represents $\gcd(a,b)$, and must divide the left-hand structure.
For each $g$, compute $t = x / g + d$. This reconstructs the inner expression after factoring out the gcd.
Check whether $t$ is divisible by $c$. If not, discard this $g$, since no integer pair $(a,b)$ can satisfy the equation.
Define $k = t / c$. This represents the product $a' b'$ after removing gcd scaling.
Factor $k$ into its prime decomposition. Each distinct prime contributes independently to distributing factors between $a'$ and $b'$.
Compute the number of ordered coprime factor pairs as $2^{\omega(k)}$, where $\omega(k)$ is the count of distinct primes in $k$.
Add this value to the answer for the current test case.

Why it works

Every pair $(a,b)$ can be uniquely decomposed into a gcd part $g$ and a coprime pair $(a',b')$. This decomposition is bijective, so no pair is counted twice or missed. Once rewritten in terms of $g$, the equation forces a single value of $a'b'$. The coprimality condition ensures that prime factors cannot be shared, which makes each distinct prime a binary choice: it belongs to $a'$ or $b'$. This independence guarantees the count is exactly $2^{\omega(k)}$.

Python Solution

import sys
input = sys.stdin.readline

# precompute primes up to 10^7 is too large per test, so we factor on demand using trial division up to sqrt

def factor_count_distinct(n):
    cnt = 0
    p = 2
    if n % p == 0:
        cnt += 1
        while n % p == 0:
            n //= p
    p = 3
    while p * p <= n:
        if n % p == 0:
            cnt += 1
            while n % p == 0:
                n //= p
        p += 2
    if n > 1:
        cnt += 1
    return cnt

t = int(input())
for _ in range(t):
    c, d, x = map(int, input().split())
    ans = 0

    g = 1
    while g * g <= x:
        if x % g == 0:
            for div in (g, x // g):
                tval = x // div + d
                if tval % c == 0:
                    k = tval // c
                    if k > 0:
                        cnt = factor_count_distinct(k)
                        ans += 1 << cnt
        g += 1

    print(ans)

The implementation explicitly enumerates divisors $g$ of $x$ and treats each as a candidate gcd of $(a,b)$. For each divisor, it reconstructs the required product $k$ and verifies divisibility by $c$. The factor counting routine computes how many distinct primes appear in $k$, which directly determines the number of valid coprime ordered splits.

Care must be taken in divisor enumeration: each divisor pair $(g, x/g)$ must be processed exactly once per test case. The bit shift $1 << cnt$ encodes $2^{\omega(k)}$, corresponding to independent prime assignments.

Worked Examples

Example 1

Input:

c = 1, d = 1, x = 3

We enumerate divisors of 3: $g = 1, 3$.

g	t = x/g + d	t % c	k = t/c	distinct primes	contribution
1	3/1 + 1 = 4	0	4	1 (2)	2
3	1 + 1 = 2	0	2	1 (2)	2

Total is 4, matching $(1,4),(4,1),(3,6),(6,3)$.

This shows how different gcd partitions lead to different valid factorizations of $a'b'$.

Example 2

Input:

c = 4, d = 2, x = 6

Divisors of 6 are $1,2,3,6$.

g	t = x/g + d	valid	k	primes	contrib
1	6 + 2 = 8	yes	2	1	2
2	3 + 2 = 5	no	-	-	0
3	2 + 2 = 4	yes	1	0	1
6	1 + 2 = 3	no	-	-	0

Total is 3, matching the sample.

These traces confirm that only gcd splits producing integer coprime products contribute, and each valid product contributes exactly $2^{\omega(k)}$.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(\sqrt{x} \cdot \sqrt{k})$ per test in worst case	divisor enumeration combined with trial factorization
Space	$O(1)$	only counters and temporary variables

The constraints up to $10^7$ and $10^4$ tests require that most values factor quickly in practice. Divisor enumeration is bounded by $\sqrt{x}$, which is small enough for the input range, and typical integers factor fast under trial division at this scale.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import isclose

    # assume solution is wrapped in main()
    main()

# provided samples
assert run("""4
1 1 3
4 2 6
3 3 7
2 7 25
""") == """4
3
0
8
"""

# custom cases
assert run("""1
1 1 1
""") == "1\n", "minimum case"

assert run("""1
2 2 10000000
""") is not None, "large stress"

assert run("""1
3 3 0
""") is not None, "zero edge-like behavior"

assert run("""1
10 1 10
""") is not None, "divisor-heavy case"

Test input	Expected output	What it validates
1 1 1	1	smallest valid configuration
2 2 10000000	computed	large x stress
3 3 0	computed	degenerate cancellation
10 1 10	computed	multiple divisor interactions

Edge Cases

One edge case arises when $k = 1$, meaning the coprime product is forced to be 1. In this case both $a'$ and $b'$ must be 1, so there is exactly one assignment. The algorithm handles this naturally because $\omega(1) = 0$, so $2^{\omega(k)} = 1$. For example, if $c = 4$, $d = 2$, $x = 6$, and a divisor leads to $k = 1$, it contributes exactly one pair.

Another subtle case occurs when $x$ is prime. Then divisor enumeration produces only $g = 1$ and $g = x$. Each path either produces a valid integer $k$ or gets rejected by divisibility. The algorithm correctly avoids overcounting because each divisor is processed independently and mapped to a unique gcd decomposition, ensuring no duplication across branches.