hem… soal menarik lagi dari TJU..
link : http://acm.tju.edu.cn/toj/showp2901.html
di problem ini, kita diminta untuk print faktorisasi prima dari hasil combinasi dua bilangan.
Misalna :
-> 10C5 = 252
-> 10C5 = 2 * 2 * 3 * 7 ( yang kita harus cetak adalah hasil ini )
problem ini bisa diselesaikan dengan mencari dahulu hasil kombinasi, kemudian difaktorisasi.. Masalahnya adalah nilai n dan c bisa mencapai 3000( kalau 3000C1500 maka nilaina tidak bisa lagi ditampung di dalam int). Oleh karena itu diperlukan suatu algoritma lain..
di sini, saya mencoba menyelesaikan dengan menggunakan teknik matematika sederhana.
misal :
n = 3000 dan c = 1500, maka nilai kombinasina adalah 3000!/(1500!)(3000-1500)! = (3000*2999*2998*…*1501)/1500!
dari sini saya mencoba looping dari 3000 sampai 1501, dan mencari faktor primana satu persatu yg kemudian disimpan ke dalam array.
untuk pembagina juga, saya melooping dari 1 sampai 1500, dan mencari faktor prima juga.
setelah mencatat semua faktor prima dari penyebut dan pembilangna, maka saya tinggal mencetak apabila prima penyebut lebih banyak dari pembilangna..
cara ini cukup cepat, karena saya mendapat waktu yang cukup baik.