n-е число що ділиться на a або b (#9018)

Аналіз алгоритму

Нехай функція $f (n)$ обчислює кількість натуральних чисел на проміжку [1; $n$ ], що діляться або на $a$ , або на $b$ . Ця кількість дорівнює

n / a + n / b - n / НСК (a, b)

Нехай $x$ – шукане $n$ -те число. Тоді $x$ має бути таким найменшим натуральним числом, що $f (x) = n$ . Його будемо шукати бінарним пошуком, починаючи з відрізка [ $left$ ; $right$ ] = [1; $1 0^{9}$ ]. Нехай $mid$ = ( $left$ + $right$ ) / 2. Якщо $f (mid) \geq n$ , то пошук слід продовжувати на відрізку [ $left$ ; $mid$ ], інакше – на відрізку [ $mid$ + 1; $right$ ].

Приклад

Розглянемо перший приклад, в якому $a = 2$ , $b = 5$ . Необхідно знайти найменше $x$ , для якого $f (x) = 10$ . Вирахуємо деякі значення:

$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;$

Найменшим розв'язком рівняння $f (x) = 10$ буде $x = 16$ .

Реалізація алгоритму

Функції обчислення НСД і НСК.

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;
}

Функція $f (n)$ повертає кількість натуральних чисел, не більших $n$ , що діляться або на $a$ , або на $b$ .

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

Читаємо вхідні дані.

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

Запускаємо бінарний пошук. Шукаємо найменше значення $left$ , для якого $f (left) = n$ .

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

Виводимо відповідь.

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

Java реалізація

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();
    }
}