ACM/ICPC Indonesia National Contest 2007

Problem B

GCD!

Time Limit: 1s

The greatest common divisor of two numbers is defined as the largest integer that divides both numbers without leaving any reminder. For example, the greatest common divisor of 8 and 12, written as GCD(8,12) is 4, as 4 is the largest integer that divides both 8 and 12 (the common divisors of 8 and 12 are 1, 2, and 4).

Meanwhile, the factorial of a natural number is the product of all positive integers less than or equal to that number. For example, the factorial of 5, written as 5! is 1*2*3*4*5, which equals to 120. By convention, 0! is 1.

Given two integers, n and k, you should find the greatest common divisor of n! and k. For example, if n = 3 and k = 10, then GCD(n!,k) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2. Write a program to find this number!

Input

Each line contains two integers, n (0 <= n <= 1,000,000,000) and k (1 <= k <= 1,000,000,000) respectively.

Output

For each line of input, output one line containing the GCD of n! and k.

Sample Input

Sample Output

Problem Setter: Suhendry Effendy

Pembahasan Problem B - GCD!

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);
    }
}

Kembali ke halaman utama

Saturday, June 16, 2007

Final Indonesia National Contest 2007 :: Problem B - GCD!