n-th integer divisible by a or b (#9018)

Algorithm Analysis

Let the function $f (n)$ compute the number of natural numbers in the interval [1; $n$ ] that are divisible by either $a$ or $b$ . This count equals

n / a + n / b - n / lcm (a, b)

Let $x$ be the sought $n$ -th number. Then $x$ must be the smallest natural number such that $f (x) = n$ . We will search for it using binary search, starting with the interval [ $left$ ; $right$ ] = [1; $1 0^{9}$ ]. Let $mid$ = ( $left$ + $right$ ) / 2. If $f (mid) \geq n$ , then the search should continue on the interval [ $left$ ; $mid$ ], otherwise – on the interval [ $mid$ + 1; $right$ ].

Example

Consider the first example, where $a = 2$ , $b = 5$ . It is necessary to find the smallest $x$ , for which $f (x) = 10$ . Let's calculate some values:

$f (15) = 15/2 + 15/5-15/10 = 7 + 3-1 = 9;$
$f (16) = 16/2 + 16/5-16/10 = 8 + 3-1 = 10;$
$f (17) = 17/2 + 17/5-17/10 = 8 + 3-1 = 10;$
$f (18) = 18/2 + 18/5-18/10 = 9 + 3-1 = 11;$

The smallest solution to the equation $f (x) = 10$ will be $x = 16$ .

Algorithm Implementation

Functions for computing GCD and LCM.

long long gcd(long long a, long long b) {
    return (b == 0) ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

The function $f (n)$ returns the number of natural numbers not greater than $n$ that are divisible by either $a$ or $b$ .

long long f(long long n) {
    return n / a + n / b - n / lcm(a, b);
}

Read the input data.

scanf("%lld %lld %lld", &a, &b, &n);

Start the binary search. Look for the smallest value of $left$ , for which $f (left) = n$ .

left = 1; right = 1e9;
while (left < right) {
    middle = (left + right) / 2;
    if (f(middle) >= n)
        right = middle;
    else
        left = middle + 1;
}

Print the answer.

printf("%lld\n", left);

Java Implementation

import java.util.*;
import java.io.*;

public class Main {
    static long gcd(long a, long b) {
        return (b == 0) ? a : gcd(b, a % b);
    }

    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    static long f(long n, long a, long b) {
        return n / a + n / b - n / lcm(a, b);
    }

    public static void main(String[] args) {
        FastScanner con = new FastScanner(new InputStreamReader(System.in));
        long a = con.nextInt();
        long b = con.nextInt();
        long n = con.nextInt();

        long left = 1, right = 1000000000;
        while (left < right) {
            long middle = (left + right) / 2;
            if (f(middle, a, b) >= n)
                right = middle;
            else
                left = middle + 1;
        }
        System.out.println(left);
    }
}

class FastScanner {
    private BufferedReader br;
    private StringTokenizer st;

    public FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
    }

    public String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public void close() throws Exception {
        br.close();
    }
}