10 10

10 5

25 6

Sample Output

8

4

2

      （1）编程思路。

      有了例1的思路2的解决方法，求排列数P（n，m）的最后一个非0数字就变得十分容易了。

      由于P(n，m) = n!/(n-m)!，就是求乘积(n-m+1)*(n-m+2)*…*(n-m+m-1)*n。因此，可以先求出1~n序列和1~(n-m)序列中质因数2、5的个数和末位数字3、7、9分别出现的次数，然后再各自相减后计算排列P(n，m)的最后一个非0数字。

      但在计算排列P(n，m)的最后一个非0数字时要特别注意一个小“陷阱”：因子2出现的次数可能小于5出现的次数，例如排列数P(26,2)=26*25，因子2的个数为1、因子5的个数为2。这种情况下，最后一个非0数字一定是5，因为5乘以任何一个奇数的末位数字总是5。此时，可以直接输出5。

      按照编程思路，如果直接改造例1中的源程序2，需要对数组的定义方式进行修改。因为0 <= N<= 20000000，所以数组空间应为int table[5][ 20000001]，定义静态数组的话，在栈空间进行存储分配，会造成栈的溢出，程序不能运行。修改数组的定义为动态数组，从而在堆空间进行存储分配。二维动态数组的定义方式为：

    int **table=new int *[5];   // 动态申请二维数组的第一维  

    for(i=0;i<=5;i++) 

         table[i]=new int [20000001]; // 动态申请二维数组的第二维 

      （2）评测结果显示为“Memory Limit Exceeded”的源程序1。

#include<iostream>  

using namespace std;  

int main()

{

       int i,t,n,m,cnt2,cnt5,cnt3,cnt7,cnt9;

       int last[4][4] ={{6,2,4,8},{1,3,9,7},{1,7,9,3},{1,9,1,9}};  

       int **table=new int *[5];   // 动态申请二维数组的第一维  

       for(i=0;i<=5;i++) 

         table[i]=new int [20000001]; // 动态申请二维数组的第二维  

       table[0][0]=table[1][0]=table[2][0]=table[3][0]=table[4][0]=0;

       for (i=1;i<=20000000;i++)

       {

              t=i;

              cnt2=cnt5=0;

              while (t%2==0)

              {

                     cnt2++;

                     t=t/2;

              }

              while (t%5==0)

              {

                     cnt5++;

                     t=t/5;

              }

        table[0][i]=table[0][i-1]+cnt2;  // 因子2的个数

              table[2][i]=table[2][i-1]+cnt5;  // 因子5的个数