n-те число, яке ділиться на a або b#9018
Увійти

n-те число, яке ділиться на a або b (Розбір)

Нехай функція обчислює кількість натуральних чисел на відрізку , які діляться або на , або на . Цю кількість можна обчислити за формулою:

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

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

Приклад

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

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

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

Функції gcd і 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;
}
C++

Функція повертає кількість натуральних чисел, що не перевищують і діляться чи на , чи на .

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

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

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

Запускаємо бінарний пошук на відрізку [left; right] = [1; 10^9]. Шукаємо найменше значення , при якому виконується умова f(left) = n.

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

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

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