子序列1由小于等于n的奇数组成，设函数getOdd(n,x)表示小于等于n的奇数中末位数字为奇数x的数的个数。而子序列2中的每个数除以2后，得到一个从1~n/2的子序列。例如，{2，4，6，8，10}中的每个数除以2，就是序列{1，2，3，4，5}，也就是说这个问题可看成一个原来问题的子问题。

       由此，可得到递推式getLast(n,x) = getLast(n/2,x) +getOdd(n,x)。

      getOdd(n,x)怎么求呢？观察小于等于n的奇数序列（有n/2个数）。按末位数字分成5组{1,11,21,31，…}，{3,13,23,33，…}，{5,15,25,35，…}，{7,17,27,37，…}，{9,19,29,39，…}，每组至少有n/10个数。由于n不一定是10的倍数，还需看看n%10>=x是否成立，成立就加1，不成立就不加1。在这5组中，末位数字为5的组中每个数都含有质因子5，要去掉5这个因子，每个数除以5后，序列又变成了{1,3,5,7,…}，该序列中n/10个数奇数，所有的奇数小于等于n/5，也就是说这个问题也看看成一个原来问题的子问题。

       由此，可得到递推式 getOdd(n,x)=n/10+(n%10>=x)+getOdd(n/5,x)。

      有了上面这两个递推式，采用递归的方法能很快求得1~n序列中末位数字为3、7、9的数的个数。

      （5）可Accepted的源程序3。

#include <iostream>  

using namespace std; 

int getFactor(int n,int k)  

{ 

    int cnt=0; 

    while(n) 

    { 

        cnt+=n/k; 

        n/=k; 

    } 

    return cnt; 

} 

int getOdd(int n,int k) 

{ 

    if (n==0) return 0; 

    return n/10+(n%10>=k)+getOdd(n/5,k);  

} 

int getLast(int n,int k) 

{ 

    if (n==0) return 0; 

    return getLast(n/2,k)+getOdd(n,k); 

} 

int main() 

{ 

       int 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}};  

       while (cin>>n>>m)

       {

             if (m == 0)

              {

                     cout<<"1"<<endl;

                     continue;

              }

        cnt2 = getFactor(n,2) - getFactor(n-m,2); 

        cnt5 = getFactor(n,5) - getFactor(n-m,5); 

        cnt3 = getLast(n,3) - getLast(n-m,3); 

        cnt7 = getLast(n,7) - getLast(n-m,7); 

        cnt9 = getLast(n,9) - getLast(n-m,9); 

        if (cnt2>=cnt5)

              {

                  cnt2=cnt2-cnt5;