My first Magazine pemrograman-kompetitif-dasar | Page 15

1.3 Contoh Soal Pemrograman Kompetitif
# include < iostream >
using namespace std ;
int main () {
long long N ;
cin >> N ;
long long num = N ;
int divisorCount = 1;
for ( long long i = 2; i * i <= num ; i ++) {
int factorCount = 0;
while ( num % i == 0) {
factorCount ++;
num /= i ;
}
divisorCount *= (1 + factorCount );
}
if ( num > 1) { // Sisa faktor
divisorCount *= 2;
}
if ( divisorCount % 2 == 0) {
cout << " lampu ␣ mati " << endl ;
} else {
cout << " lampu ␣ menyala " << endl ;
}
}
√
Karena pengecekan hanya dilakukan hingga N saja untuk melakukan faktorisasi bilangan
N, maka perhitungan dapat dilakukan di bawah 1 detik untuk N sampai 10 16 . Namun, untuk 10 18 ,
kemungkinan program masih memerlukan waktu di atas 1 detik.
1.3.3
Solusi yang Lebih Baik Lagi!
Ternyata, masih ada solusi yang lebih baik dibandingkan dengan solusi menggunakan fak-
torisasi prima. Perhatikan bahwa kita tidak perlu tahu berapa banyak pembagi bilangan N. Kita
hanya perlu tahu apakah N memiliki pembagi sebanyak ganjil atau genap.
Jika suatu bilangan, sebut saja x membagi habis N, maka otomatis
habis N. Perhatikan contoh berikut:
N
x
juga akan membagi
Jika N = 12, maka:
• Karena 1 membagi habis 12, maka
• Karena 2 membagi habis 12, maka
• Karena 3 membagi habis 12, maka
12
1
12
2
12
3
= 12 juga membagi habis 12
= 6 juga membagi habis 12
= 4 juga membagi habis 12
Dengan demikian, secara umum pembagi bilangan selalu memiliki pasangan, kecuali jika
N merupakan bilangan kuadrat, misalnya 4, 9, 16 dan seterusnya. Mengapa demikian? Jika N
5