# **LEGENDRE PTICH THỪA SỐ NGUYÊN TỐ CỦA N GIAI THỪA**
>Đọc ở đây:https://www.geeksforgeeks.org/legendres-formula-highest-power-of-prime-number-that-divides-n/

**PROBLEM**: https://lqdoj.edu.vn/problem/fctest4902
## ***Code***:

// Sàng nguyên tố
void sang(){
    FOR(i,1,N) a[i] = 1;
    FOR(i,2,N)
        if(a[i] == 1){
            v.push_back(i);
            for(ll j=i*i; j<=N; j+=i) a[j]=0;
        }
}

// Cho p và n, tìm x lớn nhất sao cho p^x chia hết cho n!
int leg(int n, int x){
    int p = x, t = 0;
    while(n >= x){
        t += n / x;
        x *= p;
    }
    return t;
}

// tính tổ hợp chập
FORA(i, v) b[i] += leg(n, i);
FORA(i, v) b[i] -= leg(n-k, i);
FORA(i, v) b[i] -= leg(k, i);

// tính ước
res=1
FORA(i, v) res *= (b[i] + 1);