Suhendry’s Blog

G - Jumlah Pembagi

Author: Eko Wibowo

Misalnya kita memiliki sebuah bilangan N = 60, pembagi dari 60 adalah: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 dan 60, yang semuanya memiliki faktor prima hanya 2, 3 atau 5, bisa juga ditulis sebagai: 2⁰3⁰5⁰, 2¹3⁰5⁰, 2⁰3¹5⁰, 2²3⁰5⁰, 2⁰3⁰5¹, 2¹3¹5⁰, 2¹3⁰5¹, 2²3¹5⁰, 2⁰3¹5¹, 2²3⁰5¹, 2¹3¹5¹, 2²3¹5¹. Jumlah dari semua bilangan tersebut adalah 2⁰3⁰5⁰ + 2⁰3⁰5¹ + 2⁰3¹5⁰ + 2⁰3¹5¹ + 2¹3⁰5⁰ + 2¹3⁰5¹ + 2¹3¹5⁰ + 2¹3¹5¹ + 2²3⁰5⁰ + 2²3⁰5¹ + 2²3¹5⁰ + 2²3¹5¹, atau bisa ditulis sebagai: (2⁰ + 2¹ + 2²) * (3⁰ + 3¹) * (5⁰ + 5¹).

Dari contoh di atas, bisa disimpulkan untuk menghitung jumlah pembagi dari suatu bilangan bulat N bisa dengan memfaktorkan N menjadi p₁^a₁ * p₂^a₂ * … * p_t^a_t dimana p adalah faktor prima dari N dan menghitung rumus:

SOD = (p₁⁰ + p₁¹ + … + p₁^a₁) * (p₂⁰ + p₂¹ + … + p₂^a₂) * … * (p_t⁰ + p_t¹ + … + p_t^a_t)

Masalah berikutnya adalah bagaimana cara menghitung p₁⁰ + p₁¹ + … + p₁^a₁ dengan cepat, karena pangkat a bisa mencapai 100,000,000 (batasan input).

Ada (setidaknya) dua cara untuk menyelesaikan masalah ini, yang pertama adalah dengan divide and conquer:

f(a,n) { // menghitung nilai dari a⁰ + a¹ + … + aⁿ
if ( n == 0 ) return 1;
if ( n mod 2 == 1) {
x = f(a,n-1);
return x + x * (a - 1) + 1 ;
}
else {
x = f(a,n/2);
return x * (x * (a - 1) + 1) + x;
}
}

Cara kedua adalah dengan menggunakan rekursi yang dimodelkan sebagai matrix

di mana elemen (1,1) dari matrix A adalah f(a,n) dan elemen (1,2) adalah aⁿ. Di sini teknik divide and conquer kembali digunakan untuk memangkatkan matrix tersebut.

• Problem A - Teks Fibonacci
• Problem B - BeSaR DaN KeCiL
• Problem C - Rentang Terbesar
• Problem D - Merakit Komputer
• Problem E - Mario Bros
• Problem F - Kaca Patri
• Problem G - Jumlah Pembagi
• Problem H - Drum Minyak Pak Ricat
• Problem I - Jumlah Pangkat
• Problem J - Ordo Keprimaan
• Medalist

Pages: 1 2 3 4 5 6 7 8 9 10 11 12