ACM 10212 The Last Non-zero Digit

數學


#include <stdio.h>

int get(int num, int div)
{
    int count = 0;
  
    while (num >= div)
    {
        count = count + num/div;
        num /= div;
    }
  
    return count;
}

int main(void)
{
    int m, n, c, d, i, rs, tmp;
  
    while (scanf("%d%d", &n, &m) == 2)
    {
        c = get(n, 5) - get(n-m, 5);
        d = get(n, 2) - get(n-m, 2);
        if (c > d)
            c = d;
        else
            d = c;
        rs = 1;
        for (i = n-m+1; i <= n; i++)
        {
            tmp = i;
            while (c > 0 && tmp%5 == 0)
                tmp /= 5, c--;
            while (d > 0 && tmp%2 == 0)
                tmp /= 2, d--;
            rs = (rs*tmp) % 10;
        }

        printf("%d\n", rs);
    }
  
    return 0;
}