a və ya b-yə bölünən n-əci ədəd#9018
Daxil ol

a və ya b-yə bölünən n-əci ədəd (Həll təhlili)

Güman edək ki, funksiyası intervalındakı təbii ədədlərin sayını hesablayır, hansı ki, və ya -yə bölünür. Bu say aşağıdakı düsturla hesablana bilər:

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

Tutaq ki, axtarılan -ci ədəddir, hansı ki və ya -yə bölünür. O zaman kiçik, təbii ədəddir ki, onun üçün f(x) = n şərti ödənir. Onu [left; right] = [1; 10^9] intervalında ikili axtarış ilə tapacağıq. Hər addımda mid = (left + right) / 2 hesablanır. Əgər f(mid) \ge n, axtarışı sol altintervalda davam edirik [left; mid], əks halda sağ altintervalda [mid + 1; right].

Nümunə

Birinci nümunəni nəzərdən keçirək, burada a = 2, b = 5. f(x) = 10 şərtini təmin edən kiçik dəyərini tapmaq lazımdır. Müəyyən üçün funksiyasının dəyərlərini hesablayırıq:

f(x) = 10 tənliyinin kiçik həlli x = 16 olacaq.

Alqoritmin reallaşdırılması

gcd və lcm funksiyaları müvafiq olaraq EVF və BOQ-ni hesablayır.

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++

funksiyası -dən böyük olmayan və və ya -yə bölünən təbii ədədlərin sayını qaytarır.

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

Daxil olan məlumatları oxuyuruq.

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

[left; right] = [1; 10^9] intervalında ikili axtarışı işə salırıq. f(left) = n şərtinin ödənildiyi kiçik dəyərini tapırıq.

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

Cavabı çıxarırıq.

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

Java reallaşdırılması

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