LightOj 1090 - Trailing Zeroes (II)---求末尾0的个数

题目链接：http://lightoj.com/volume_showproblem.php?problem=1090

题意：给你四个数 n, r, p, q 求C(n, r) * p^q的结果中末尾0的个数;(1<=n, r, p, q <= 10^6, r ≤ n)

要求末尾0的个数，一定和2和5有关，例如num1 * num2结果中末尾0的个数可以表示成min(num1中2的个数+num2中2的个数, num1中5的个数+num2中5的个数);

对于C(n, r)中0的2的个数可以写成f[n]-f[r]-f[n-r]，其中f[i]表示i!中2的个数;打表求出 f 即可

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

typedef long long LL;

#define N 1000001

using namespace std;

const double eps = 1e-;

int f[N], g[N]; ///f[i]表示i!*有多少个2, g[i]表示i!有多少个5;

void Init()

{

    int x = , y = ;

    for(int i=; i<N; i++)

    {

        int n = i;

        while(n% == )

        {

            x ++;

            n /= ;

        }

        n = i;

        while(n% == )

        {

            y ++;

            n /= ;

        }

        f[i] = x;

        g[i] = y;

    }

}

int main()

{

    Init();

    int T, t = ;

    scanf("%d", &T);

    while(T --)

    {

        int p, q, n, r;

        scanf("%d %d %d %d", &n, &r, &p, &q);

        int ans1, ans2, ans;

        ans1 = f[n]-f[r]-f[n-r] + q*(f[p]-f[p-]);

        ans2 = g[n]-g[r]-g[n-r] + q*(g[p]-g[p-]);

        ans = min(ans1, ans2);

        printf("Case %d: %d\n", t++, ans);

    }

    return ;

}