14. Pak Dengklek sedang mengecek berkas OSP Komputer 2019. Salah satu soalnya berbunyi seperti ini:
"Berapa banyak bilangan di antara [1 .. 1000] (inklusif) yang habis dibagi 3 dan habis dibagi x?"
Pak Dengklek tahu bahwa jawabannya adalah 393, namun ia lupa berapakah nilai x. Pak Dengklek hanya ingat bahwa 3 dan x pasti relatif prima. Dua bilangan dikatakan relatif prima apabila faktor persekutuan terbesar dari kedua bilangan tersebut adalah 1. Berapakah nilai x?
Pembahasan Soal OSP Informatika Komputer 2019 No 14
Misalkan ai adalah bilangan yang memenuhi syarat. Dimana i={1,2,3,...393}
ai habis dibagi 3 dan x serta 3 dan x relatif prima sehingga 3 dan x adalah faktor dari ai dan x bulat. Maka ai dapat dicari dengan rumus
ai=i*3*x
a393=393*3x=1179x
Karena a393<=1000 x tidak ada jawabannya.
Ini akan berbeda jika pernyataan sebelumnya "Berapa banyak bilangan di antara [1 .. 1000] (inklusif) yang habis dibagi 3 atau habis dibagi x" karena jika "dan" ai harus memenuhi 2 syarat yaitu ai habis dibagi 3, ai habis dibagi x. Tetapi jika menggunakan "atau" hanyar perlu memenuhi salah satu bisa juga memenuhi keduanya.
Untuk mencari bilangan yang habis dibagi 3 =1000/3=333(dibulatkan kebawah)
Selanjutnya 1-1000 pasti ada kelipatan 3x sehingga
60=1000/x(dibulatkan kebawah)-1000/3x(dibulatkan kebawah)
Kita mulai cari bilangan prima terkecil yang memenuhi persamaan diatas sehingga didapat x=11
0 komentar:
Post a Comment