n-ci ədəd a və ya b-ə bölünən (#9018)

Alqoritm Analizi

Funksiya $f (n)$ , [1; $n$ ] aralığında $a$ və ya $b$ -yə bölünən təbii ədədlərin sayını hesablasın. Bu say aşağıdakıya bərabərdir:

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

Axtarılan $n$ -ci ədəd $x$ olsun. Onda $x$ , $f (x) = n$ olacaq ən kiçik təbii ədəd olmalıdır. Biz onu ikili axtarışla tapacağıq, başlanğıc intervalı [ $left$ ; $right$ ] = [1; $1 0^{9}$ ] olaraq götürəcəyik. $mid$ = ( $left$ + $right$ ) / 2 olsun. Əgər $f (mid) \geq n$ isə, axtarış [ $left$ ; $mid$ ] intervalında davam etməlidir, əks halda – [ $mid$ + 1; $right$ ] intervalında.

Nümunə

Birinci nümunəni nəzərdən keçirək, burada $a = 2$ , $b = 5$ . $f (x) = 10$ olan ən kiçik $x$ -i tapmaq lazımdır. Bəzi dəyərləri hesablayaq:

$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$ tənliyinin ən kiçik həlli $x = 16$ olacaq.

Alqoritm Tətbiqi

ƏBOB və ƏKOB hesablamaq üçün funksiyalar.

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

Funksiya $f (n)$ , $n$ -dən kiçik və ya ona bərabər olan təbii ədədlərin sayını qaytarır ki, bu ədədlər ya $a$ -ya, ya da $b$ -yə bölünür.

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

Giriş məlumatlarını oxu.

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

İkili axtarışa başla. $f (left) = n$ olan ən kiçik $left$ dəyərini tap.

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

Cavabı çap et.

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

Java Tətbiqi

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