poj 1150 The Last Non-zero Digit-白红宇

poj 1150 The Last Non-zero Digit

阅读量：5159 次

发布时间：2019-06-13

本文共 2424 字，大约阅读时间需要 8 分钟。

The Last Non-zero Digit

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5363		Accepted: 1642

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 1010 525 6

Sample Output8

42 题意：求A(n,m)的最后一个非零末尾，A(n,m)即n!/(n-m)! 思路：先把A(n,m)中的所有2和5因子提取出来，考虑剩余部分的积的末尾，这可以表示为A(n,m)/(2^a*5^b)

，其中a,b为2，5的因子个数，那么剩余部分的因子结尾一定为3，7，9，可以先把这部分的乘积的末尾求出来(3，7，9的n次方的末尾数都是4个1循环，方便求得)，之后再结合因子2和5，若5的个数多于2,最终结尾一定为5，若2的个数多于5，多出来的2^(a-b)

末尾也是4个数一循环，可以方便求出来。 那么现在的关键是如何求得因子结尾是3，7，9的那些数的个数,我么可以将n!分成两个数列，奇数列和偶数列，先看奇数列,奇数列中每间隔10都会出现一个3，7，9的数，最后间隔小于10的部分则考虑剩余部分间隔是否大于x(3,7,9)，若x大于间隔，则存在一个以x结尾的因子.考虑到数列中有5的倍数，n/5递归数列继续以上的操作。 偶数列不断递归除以2也能得到奇数列。 AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define INF 0x3f3f3f3fconst int N_MAX = 20000000+4;int n,m;//计算n!中x的因子个数int prime_num(int n, int x) { int num = 0; while(n) { num += n / x; n /= x; } return num;}//计算n!以3,7,9结尾的因子的个数int odd_end_with(int n,int x) { if (n == 0)return 0; return n / 10 +((n%10)>=x)+odd_end_with(n / 5, x) ;}int end_with(int n,int x) { if (n == 0)return 0; return odd_end_with(n,x) + end_with(n/2,x);}int table[4][4] = { 6, 2, 4, 8,//2 1, 3, 9, 7,//3 1, 7, 9, 3,//7 1, 9, 1, 9//9};int main() { while (scanf("%d%d",&n,&m)!=EOF) { int two = prime_num(n, 2) - prime_num(n - m, 2); int five = prime_num(n, 5) - prime_num(n - m, 5); if (five > two) { printf("5\n"); continue; } int three = end_with(n, 3) - end_with(n - m, 3); int seven = end_with(n, 7) - end_with(n - m, 7); int nine = end_with(n, 9) - end_with(n - m, 9); int res = 1; if(two>five)res *= table[0][(two - five) % 4]; res *= table[1][three % 4]; res *= table[2][seven % 4]; res *= table[3][nine % 4]; res %= 10; printf("%d\n",res); } return 0;}