My first Magazine pemrograman-kompetitif-dasar | Page 14

1 Perkenalan Pemrograman Kompetitif
Untuk masukan N, program sederhana ini melakukan N buah pengecekan. Artinya pada kasus
terburuk, program tersebut akan melakukan N = 10 18 buah pengecekan! Jika kita asumsikan
komputer sekarang dapat melakukan 10 8 operasi per detik, program ini memerlukan waktu 10
tahun untuk menyelesaikan hitungan! Program ini hanya akan bekerja untuk nilai N yang kecil.
Untuk N yang lebih besar, misalnya N = 10 9 , kemungkinan besar diperlukan waktu lebih dari 1
detik. Solusi ini tidak akan mendapatkan nilai penuh, atau bahkan 0, tergantung skema penilaian
yang digunakan.
1.3.2
Solusi yang Lebih Baik
Dengan sedikit observasi, yang sebenarnya perlu dilakukan adalah menghitung banyaknya
pembagi dari N. Apabila banyaknya pembagi ganjil, berarti pada akhirnya lampu di ruangan ke-N
akan menyala. Demikian pula sebaliknya, apabila genap, berarti lampu di ruangan ke-N akan mati.
Diperlukan suatu cara untuk menghitung banyaknya pembagi dari N dengan efisien. Salah
satu caranya adalah dengan melakukan faktorisasi prima terlebih dahulu. Misalkan untuk N = 12,
maka faktorisasi primanya adalah 2 2 × 3. Berdasarkan faktorisasi prima ini, suatu bilangan
merupakan pembagi dari 12 apabila dipenuhi:
• Memiliki faktor 2 maksimal sebanyak 2.
• Memiliki faktor 3 maksimal sebanyak 1.
• Tidak boleh memiliki faktor lainnya.
Sebagai contoh, berikut daftar seluruh pembagi dari 12:
•
•
•
•
•
•
1 = 2 0 × 3 0
2 = 2 1 × 3 0
3 = 2 0 × 3 1
4 = 2 2 × 3 0
6 = 2 1 × 3 1
12 = 2 2 × 3 1
Banyaknya pembagi dari 12 sebenarnya sama saja dengan banyaknya kombinasi yang bisa
dipilih dari {2 0 , 2 1 , 2 2 } dan {3 0 , 3 1 }. Banyaknya kombinasi sama dengan mengalikan banyaknya
elemen pada tiap-tiap himpunan. Sehingga, banyaknya cara adalah 3 × 2 = 6 cara. Dengan
demikian, banyaknya pembagi dari 12 adalah 6. Cara ini juga berlaku untuk nilai N yang lain.
Misalnya N = 172.872 = 2 3 × 3 2 × 7 4 . Berarti banyak pembaginya adalah 4 × 3 × 5 = 60.
Secara umum, banyaknya pembagi dari:
N = a 1 p 1 × a 2 p 2 × a 3 p 3 × ... × a k p k
adalah:
(1 + p 1 ) × (1 + p 2 ) × (1 + p 3 ) × ... × (1 + p k )
Jadi pencarian banyaknya pembagi dapat dilakukan dengan melakukan faktorisasi prima pada
N, lalu hitung
banyak pembaginya dengan rumus tersebut. Anda cukup melakukan pengecekan
√
sampai N saja untuk melakukan faktorisasi bilangan N.
Berikut adalah implementasi solusi ini dalam C++:
4