uva 568 just the facts-CSDN博客

本文链接：https://blog.csdn.net/chengouxuan/article/details/7188245

Just the Facts

The expression N !, read as `` N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,

N	N!
`0`	`1`
`1`	`1`
`2`	`2`
`3`	`6`
`4`	`24`
`5`	`120`
`10`	`3628800`

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for ( $0 \le N \le 10000$ ). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce ``2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces. For each integer N , you should read the value and compute the last nonzero digit of N !.

Output

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N , right-justified in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain `` -> " (space hyphen greater space). Column 10 must contain the single last non-zero digit of N !.

Sample Input

Sample Output

#include <cstdio>
#include <cstdlib>
#include <cassert>


int count_twos (int);

int count_fives (int);

int count_fives_odds (int);

int last_digit_without_2_or_5 (int);

int last_digit_without_2_or_5_odds (int);

int last_nonzero (int);


int count_twos (int n)
{
    int ret = 0;
    if (n < 2) {
        ret = 0;
    } else {
        ret = n / 2 + count_twos (n / 2);
    }

    return ret;
}

int count_fives_odds (int n)
/*
 * parameter @n means: 1, 3, 5, ..., n. (an odd array)
 */
{
    int ret = 0;
    if (n < 5) {
        ret = 0;
    } else {
        ret = (n + 5) / 10 + count_fives_odds (n / 5);
    }

    return ret;
}

int count_fives (int n)
/*
 * parameter @n means: 1, 2, 3, ..., n.
 */
{
    int ret = 0;
    if (n < 5) {
        ret = 0;
    } else {
        ret = (n + 5) / 10 + count_fives_odds (n / 5) + count_fives (n / 2);
    }

    return ret;
}

int last_digit_without_2_or_5_odds (int n)
/*
 * parameter @n means: 1, 3, 5, ..., n. (an odd array)
 */
{
    if (n < 1) {
        return 1;
    }

    if (n % 2 == 0) {
        // 'n' will never be an even, fix it.
        --n;
    }

    static int loop3[] = {1, 3, 9, 7};
    int x = loop3[(n + 7) / 10 % 4];

    static int loop7[] = {1, 7, 9, 3};
    int y = loop7[(n + 3) / 10 % 4];

    static int loop9[] = {1, 9};
    int z = loop9[(n + 1) / 10 % 2];

    int w = last_digit_without_2_or_5_odds (n / 5);

    return (x * y * z * w) % 10;
}

int last_digit_without_2_or_5 (int n)
/*
 * parameter @n means: 1, 2, 3, ..., n.
 */
{
    if (n < 1) {
        return 1;
    }

    static int loop3[] = {1, 3, 9, 7};
    int x = loop3[(n + 7) / 10 % 4];

    static int loop7[] = {1, 7, 9, 3};
    int y = loop7[(n + 3) / 10 % 4];

    static int loop9[] = {1, 9};
    int z = loop9[(n + 1) / 10 % 2];

    int v = last_digit_without_2_or_5_odds (n / 5);
    int w = last_digit_without_2_or_5 (n / 2);

    return (x * y * z * v * w) % 10;
}

int last_nonzero (int n)
{
    int twos = count_twos (n);
    int fives = count_fives (n);
    int remaining_twos = twos - fives; // number of remaining twos
    assert (remaining_twos >= 0);

    static int loop2[] = {6, 2, 4, 8};
    int x = 1;
    if (remaining_twos > 0) {
        x = loop2[remaining_twos % 4];
    }

    int y = last_digit_without_2_or_5 (n);

    return (x * y) % 10;
}

int main()
{
    int n;
    while (scanf ("%d", &n) == 1) {
        printf ("%5d -> %d\n", n, last_nonzero (n));
    }
    return 0;
}