Felix Halim .NET  
Google 
Name:  Message:

Problem B - GCD!

Complete Problem Statement here

Hitunglah GCD(n!,k)

GCD (Greatest Common Divisor) dalam bahasa Indonesia adalah FPB (Faktor Persekutuan Terbesar). Untuk mencari GCD(A,B) anda bisa memfaktorisasi A dan B dalam bentuk faktor-faktor prima mereka, dan kemudian memilih faktor berpangkat paling kecil dan mengalikannya kembali.

Contoh:

A = 543312
B = 24570
GCD(A,B) = ?

Kita bisa faktorisasi A dan B menjadi faktor prima mereka:

A = 543312 =  2^4 * 3^2       * 7^3 * 11
B = 24570  =  2^1 * 3^3 * 5^1 * 7^1      * 13

Berikutnya, untuk setiap faktor prima yang bersekutu (common) antara A dan B,
ambil yang berpangkat lebih kecil, kalikan semuanya, itulah hasil GCD(A,B):

GCD(A,B) = 2^1 * 3^2 * 7^1 = 126

Ok, itu gampang... tapi pertanyaannya bukan GCD(N,K) tetapi GCD(N!,K). Bagaimana sekarang?

Untuk ini, anda perlu jurus baru:

Cara menghitung banyaknya faktor X di dalam N faktorial.
Ada cara cepat menghitung hal tersebut, anda bisa lihat artikelnya disini. (blum sempet nyari, internet bapuk)
Setelah anda tahu jurus ini, sisanya sama seperti cara diatas:
Untuk setiap faktor prima P dari K, anda cari ada berapa faktor prima P dalam N!
Lalu ambil yang berpangkat terkecil, kalikan ke dalam hasil akhir.
Silahkan lihat code dibawah untuk lebih jelasnya.

Ada satu trik lagi untuk menghindari time limit dalam pencarian faktor prima P dari K:

Carilah hanya sampai square-root dari K
Karena lebih dari itu, K sudah pasti bilangan prima.

#include <stdio.h>

// ini adalah jurus baru yang dimaksud diatas:
// menghitung jumlah faktor x dalam n!
int factorialPower(int n, int x){
    int res = 0;
    while (n>0){
        res += n/x;
        n /= x;
    }
    return res;
}

int main(){
    int n, k, i, p;

    while (scanf("%d %d",&n,&k)!=EOF){
        int result = 1; // GCD dari 2 bilangan positive apapun minimal adalah 1

        // kita hanya perlu looping p dari 2 .. sqrt(k)
		// untuk mencari faktor-faktor prima p dari k.
        for (p=2; p*p <= k; p++){
            int pPower = 0;
            while (k % p == 0){
                k /= p;   // p disini adalah bilangan prima di penjelasan diatas
                pPower++; // mencari berapa banyak faktor p dalam k
            }
            
            // memilih faktor yang berpangkat lebih kecil antara faktor-faktor dari k
            // dengan faktor-faktor dari n!, tampung pangkat terkecilnya di pPower
            if (pPower > factorialPower(n,p))
                pPower = factorialPower(n,p);

            // kalikan p ke hasil sebanyak pangkat terkecil yang bersekutu (pPower)
            for (i=0; i<pPower; i++) result *= p;
        }

        // sisa k disini adalah bilangan prima (berpangkat 1) dan kalau k lebih kecil
        // atau sama dengan n, maka k termasuk bagian dari GCD
        if (k <= n) result *= k;
        printf("%d\n",result);
    }
}

Lihat problem lain:

  1. Minimum Swap
  2. GCD!
  3. Playing With Domino
  4. Email from the Professor
  5. Panda Number
  6. Jakarta Traffic Jam
  7. Sultan's Land
  8. Tree Median
Kembali ke halaman utama

© Felix Halim 2009 (Loaded in 0.00204 secs)