PKU 1150 The Last Non-zero Digit

The Last Non-zero Digit
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 2087
Accepted: 480
Description
In this problem you will be given two decimal integer number N, M. You will have to find the last non-zero digit of the
NP
M.This means no of permutations of N things taking M at a time.
Input
The input contains several lines of input. Each line of the input file contains two integers N (0 <= N<= 20000000), M (0 <= M <= N).
Output
For each line of the input you should output a single digit, which is the last non-zero digit of
NP
M. For example, if
NP
M is 720 then the last non-zero digit is 2. So in this case your output should be 2.
Sample Input

10 10
10 5
25 6

Sample Output

8
4
2

Source
uva 10212
2, 5의 개수를 고려한 후에 차례로 해답을 구하다

void odd(int l,int r)

{

    int head=l,rear=r;

    while((head%5||!(head&0x1))&&head<=r)head++;//첫 번째 5의 배수를 찾아서 홀수입니다

    if(head<=r)

    {

        while((rear%5||!(rear&0x1)))rear--;

        cnt5+=(rear-head)/10+1;//통계 모든 5, 예를 들어 기수열에 5, 7, 9, 11, 13, 15...그러면 (15-5)/10+1=2, 2개의 5를 계산한 후에 계속해서 5의 개수를 계산한다

        odd(head/5,rear/5);

    }

    head=l+(!(l&0x1));

    rear=r;

    while((rear%10)!=(head%10))rear--;

    if(((rear-head)/10)&0x1)ans=(ans*9)%10;//순환군은 홀수(1*3*7*9)mod10=9;

    while(rear<=r)

    {

        if(rear%5)

            ans=(ans*(rear%10))%10;

        rear+=2;

    }

}

void split(int l,int r)

{

    if(l==r)

    {

        while(l%2==0)l/=2,cnt2++;

        while(l%5==0)l/=5,cnt5++;

        ans=(ans*(l%10))%10;

        return;

    }

    int head=(l+(l&0x1))>>1,rear=r>>1;

    cnt2+=(rear-head)+1;

    split(head,rear);

    odd(l,r);

}