Least Common Multiple

Q: Apa rumus KPK dari dua bilangan?

lcm(a, b) = a × b / gcd(a, b) , dihitung sebagai a / gcd(a, b) × b agar tidak ada nilai sementara yang melebihi hasilnya. Untuk 4 dan 6 , gcd-nya adalah 2 , dan 4 / 2 × 6 = 12 .

Q: Berapa kompleksitas waktu untuk menghitung KPK?

Dengan rumus gcd, kompleksitas waktunya O(log(min(a, b))) , yaitu biaya algoritma Euclid, dan kompleksitas ruangnya O(1) . Melangkah melalui kelipatan bilangan yang lebih besar membutuhkan O(min(a, b)) , sedangkan menghitung satu per satu membutuhkan O(lcm(a, b)) .

Q: Bagaimana cara mencari KPK dari lebih dari dua bilangan?

Lipat list-nya: lcm(a, b, c) = lcm(lcm(a, b), c) . Untuk [4, 6, 10] , lcm(4, 6) = 12 dan lcm(12, 10) = 60 . Nilai yang terus diperbarui bertambah dengan cepat, jadi gunakan bilangan bulat 64-bit jika list-nya panjang.

PemulaMatematika dan simulasi

+10

Kamu mendapatkan dua bilangan bulat positif a dan b. Kembalikan kelipatan persekutuan terkecilnya: bilangan bulat positif terkecil yang habis dibagi oleh a dan b.

Fungsi

lcm(a: integer, b: integer) → integer

ainteger: bilangan bulat positif pertama
binteger: bilangan bulat positif kedua
Mengembalikaninteger: bilangan bulat positif terkecil yang merupakan kelipatan dari a dan b

Batasan

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
Jawabannya muat dalam bilangan bulat bertanda 32-bit: lcm(a, b) ≤ 2³¹-1. Hasil kali a × b mungkin tidak muat.

Contoh

Input: a = 4b = 6
Output: 12
Penjelasan: Kelipatan 6 dimulai dari 6, 12, 18; kelipatan 4 dimulai dari 4, 8, 12. Angka pertama yang ada di kedua daftar adalah 12.

Input: a = 7b = 3
Output: 21
Penjelasan: 7 dan 3 tidak memiliki faktor lain selain 1 yang sama, jadi kelipatan persekutuan terkecilnya adalah hasil kali keduanya, 21.

Input: a = 15b = 45
Output: 45
Penjelasan: 15 membagi habis 45, jadi 45 sudah merupakan kelipatan keduanya, dan tidak ada kelipatan 45 yang lebih kecil.

Pertanyaan lanjutan

Bisakah kamu mencari gcd tanpa pembagian atau sisa sama sekali, hanya dengan pengurangan dan membagi dua?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Kelipatan persekutuan terkecil dan faktor persekutuan terbesar memiliki hubungan berikut: gcd(a, b) × lcm(a, b) = a × b. Jadi, jawaban cepatnya adalah a × b / gcd(a, b). Hasil perkaliannya bisa mencapai 10^12 dan melebihi batas bilangan bulat 32-bit meskipun hasil akhirnya masih muat, jadi bagi dengan gcd sebelum mengalikan.

Hitung naik mulai dari angka yang lebih besar

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Jawabannya setidaknya sebesar bilangan yang lebih besar. Mulai dengan m pada max(a, b) lalu tambahkan 1 sampai kedua bilangan membagi habisnya. Kamu mencoba kandidat dalam urutan menaik, jadi hasil pertama yang cocok adalah yang terkecil. Untuk 4 dan 6, kamu mencoba dari 6 sampai 11 dan berhenti di 12. Perulangannya selalu berakhir karena a × b adalah kelipatan persekutuan.

Jumlah percobaannya kira-kira sebesar jawaban. Untuk bilangan prima 46337 dan 46327, jawabannya adalah 2146654199, lebih dari dua miliar percobaan.

Algoritma

Tetapkan m ke nilai yang lebih besar antara a dan b.
Selama m % a atau m % b tidak sama dengan 0, tambahkan 1 ke m.
Kembalikan m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Langkahi kelipatan bilangan yang lebih besar

Intuisi

Jawabannya harus merupakan kelipatan dari bilangan yang lebih besar, big, jadi loncati big, 2 × big, 3 × big, lalu berhenti pada bilangan pertama yang habis dibagi oleh bilangan yang lebih kecil. Untuk 4 dan 6, kamu mencoba 6, lalu 12.

Karena small × big selalu merupakan kelipatan persekutuan, perulangan berjalan paling banyak min(a, b) kali, paling banyak satu juta kali di sini. Itu cukup cepat untuk batasan ini, tetapi jumlahnya tetap bertambah seiring masukan. Jika angkanya mencapai 10^18, cara ini tidak akan cukup cepat.

Algoritma

Misalkan big adalah angka yang lebih besar dan small adalah angka yang lebih kecil.
Atur m = big.
Selama m % small bukan 0, tambahkan big ke m.
Kembalikan m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Bagi dengan FPB, lalu kalikan

Intuisi

Uraikan kedua bilangan menjadi faktor prima. Untuk setiap bilangan prima, gcd mengambil pangkat yang lebih kecil dari kedua pangkatnya, sedangkan lcm mengambil yang lebih besar, sehingga keduanya menggunakan setiap faktor dari a dan b tepat satu kali: gcd × lcm = a × b. Untuk 4 = 2² dan 6 = 2 × 3, gcd adalah 2 dan lcm adalah 2² × 3 = 12.

Algoritma Euclid menemukan gcd dalam O(log(min(a, b))) langkah. Lalu hitung a / gcd × b dengan urutan tersebut: gcd membagi a tanpa sisa, jadi tidak ada yang hilang dan setiap langkah tidak melebihi hasilnya. a × b / gcd melampaui batas bilangan bulat 32-bit saat a = b = 10^6, ketika hasil kalinya adalah 10^12 dan hasilnya hanya 10^6.

Algoritma

Salin a dan b ke dalam x dan y.
Selama y bukan 0, ganti (x, y) dengan (y, x % y). Sekarang x adalah gcd.
Bagi a dengan x.
Kalikan hasilnya dengan b dan kembalikan.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Jebakan dan kasus tepi

Menghitung a × b terlebih dahulu. Di Java, C, C++, C# dan Rust, hasil perkalian dua angka yang mendekati 10^6 melampaui batas integer 32-bit dan hasilnya salah atau negatif (build debug Rust mengalami panic), meskipun lcm masih muat.
Membagi menggunakan bilangan floating point. Hasilnya bisa berupa 2.146654199E9 atau kehilangan digit terakhirnya. Gunakan integer untuk semuanya.
Menjalankan perulangan Euclid pada a dan b itu sendiri. Setelahnya, keduanya berisi gcd dan 0, jadi gunakan salinannya.
Menganggap jawabannya adalah a × b. Ini hanya berlaku jika kedua angka tidak memiliki faktor yang sama: lcm(4, 6) adalah 12, bukan 24.

Pertanyaan yang sering diajukan3

Apa rumus KPK dari dua bilangan?

lcm(a, b) = a × b / gcd(a, b), dihitung sebagai a / gcd(a, b) × b agar tidak ada nilai sementara yang melebihi hasilnya. Untuk 4 dan 6, gcd-nya adalah 2, dan 4 / 2 × 6 = 12.

Berapa kompleksitas waktu untuk menghitung KPK?

Dengan rumus gcd, kompleksitas waktunya O(log(min(a, b))), yaitu biaya algoritma Euclid, dan kompleksitas ruangnya O(1). Melangkah melalui kelipatan bilangan yang lebih besar membutuhkan O(min(a, b)), sedangkan menghitung satu per satu membutuhkan O(lcm(a, b)).

Bagaimana cara mencari KPK dari lebih dari dua bilangan?

Lipat list-nya: lcm(a, b, c) = lcm(lcm(a, b), c). Untuk [4, 6, 10], lcm(4, 6) = 12 dan lcm(12, 10) = 60. Nilai yang terus diperbarui bertambah dengan cepat, jadi gunakan bilangan bulat 64-bit jika list-nya panjang.

def lcm(a, b):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

a = 4
b = 6

Output yang diharapkan

Least Common Multiple

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Hitung naik mulai dari angka yang lebih besar

Langkahi kelipatan bilangan yang lebih besar

Bagi dengan FPB, lalu kalikan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa