// PlayZero.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace ::std;

// type IsTimesOfSomeNum
// 加上对nBase = 2时的偏特化处理会使编译器更痛苦一点，PlayFactorialTailZero能算的最大数小1为945
//template < unsigned long nNum, unsigned long nBase > struct IsTimesOfSomeNum;

//template < unsigned long nNum >
//struct IsTimesOfSomeNum< nNum, 2 >
//{
// enum { result = ( 0 != ( nNum & 0x1 ) ) };
//};

template < unsigned long nNum, unsigned long nBase >
struct IsTimesOfSomeNum/*< nNum, nBase >*/
{
enum { result = ( 0 == ( nNum % nBase ) ) };
};


// type TimesOfSomeNum
template < unsigned long nNum, unsigned long nBase > struct TimesOfSomeNum;

template < unsigned long nBase >
struct TimesOfSomeNum< 0, nBase >
{
enum { result = 0 };
};

template < unsigned long nBase >
struct TimesOfSomeNum< 1, nBase >
{
enum { result = 0 };
};

template < unsigned long nNum, unsigned long nBase >
struct TimesOfSomeNum< nNum, nBase >
{
enum { result =
IsTimesOfSomeNum< nNum, nBase >::result ? typename TimesOfSomeNum< nNum / nBase, nBase >::result + 1 : 0
};
};

// type PlayFactorialTailZero
template < unsigned long nMax > struct PlayFactorialTailZero;

template <>
struct PlayFactorialTailZero< 0 >
{
enum { nTimesOfTwo = 0 };
enum { nTimesOfFive = 0 };

enum { result = 0 };
};

template <>
struct PlayFactorialTailZero< 1 >
{
enum { nTimesOfTwo = 0 };
enum { nTimesOfFive = 0 };

enum { result = 0 };
};

template < unsigned long nMax >
struct PlayFactorialTailZero< nMax >
{
enum { nTimesOfTwo =
TimesOfSomeNum< nMax, 2 >::result
+ typename PlayFactorialTailZero< nMax - 1 >::nTimesOfTwo
};
enum { nTimesOfFive =
TimesOfSomeNum< nMax, 5 >::result
+ typename PlayFactorialTailZero< nMax - 1 >::nTimesOfFive
};

enum { result = nTimesOfFive < nTimesOfTwo ? nTimesOfFive : nTimesOfTwo };
};

// type PlayFactorialTailZeroEx
// 俺的编译器里PlayFactorialTailZero只能算到946，再大的话编译器编译输出信息如下:>，
//fatal error C1202: recursive type or function dependency context too complex
// 因此采用分段的方法从新设计PlayFactoriaTailZero。。。
template < unsigned long nMax, unsigned long nMin > struct PlayFactorialTailZeroEx;

template < unsigned long nMax >
struct PlayFactorialTailZeroEx< nMax, nMax >
{
enum { nTimesOfTwo = TimesOfSomeNum< nMax, 2 >::result };
enum { nTimesOfFive = TimesOfSomeNum< nMax, 5 >::result };

enum { result = nTimesOfFive < nTimesOfTwo ? nTimesOfFive : nTimesOfTwo };
};

template < unsigned long nMax, unsigned long nMin >
struct PlayFactorialTailZeroEx< nMax, nMin >
{
enum { nTimesOfTwo =
TimesOfSomeNum< nMax, 2 >::result
+ typename PlayFactorialTailZeroEx< nMax - 1, nMin >::nTimesOfTwo
};
enum { nTimesOfFive =
TimesOfSomeNum< nMax, 5 >::result
+ typename PlayFactorialTailZeroEx< nMax - 1, nMin >::nTimesOfFive
};

enum { result = nTimesOfFive < nTimesOfTwo ? nTimesOfFive : nTimesOfTwo };
};


int _tmain(int argc, _TCHAR* argv[])
{
// 当然算法就是这样的(找2和5的因子对)，不用这种在编译期运算的模板方法，就不必一定使用
// 第归，也就不会出现数太大（如>946）时编译器提示的编译错误。
cout << _T("946的阶乘结果数字末尾0的个数是: ") << PlayFactorialTailZero< 946 >::result << endl;

cout << _T("1000的阶乘结果数字末尾0的个数是: ") << ( PlayFactorialTailZeroEx< 1000, 501 >::result + PlayFactorialTailZeroEx< 500, 1 >::result ) << endl;

// 以下被注释掉的是因为的确超出了编译器的能力。。。
unsigned long nResult =
//PlayFactorialTailZeroEx< 5000, 4501 >::result + PlayFactorialTailZeroEx< 4500, 4001 >::result
//PlayFactorialTailZeroEx< 4000, 3501 >::result + PlayFactorialTailZeroEx< 3500, 3001 >::result
//+ PlayFactorialTailZeroEx< 3000, 2501 >::result + PlayFactorialTailZeroEx< 2500, 2001 >::result
PlayFactorialTailZeroEx< 2000, 1501 >::result + PlayFactorialTailZeroEx< 1500, 1001 >::result
+ PlayFactorialTailZeroEx< 1000, 501 >::result + PlayFactorialTailZeroEx< 500, 1 >::result;
cout << _T("2000的阶乘结果数字末尾0的个数是: ") << nResult << endl;

return 0;
}