acm题求教，高手上啊！！
在所有的n位正整数中有多少个数满足“5”在这个数里面出现偶数次

输入包含测试数据，每层数据占一行，为一个整数n（ 2=<n<=1000000）
输入0结束

输出每组数据占一行，为有偶数个 数位上的数字是5的整数的个数，由于这个结果非常大，要输出其模除10的8
次方的结果
测试数据
输入
2
0
输出
43

[解决办法]
lz的样例就十分奇怪，需要clarify一下。43个是哪43个

按照偶自己的理解的话，
令d[n]为<=n位的答案
d[n]=(10^n + 8^n)/2
然后最后输出d[n]-d[n-1]
[解决办法]
n为奇数时
设D(n) = c(n,0)*9^n + c(n,2)*9^(n-2) + ......c(n,n-1)*9^1

考虑第一位为0的情况
f(n) = D(n) - D(n-1)

偶数时也差不多，LZ可以自己推导一下