时间限制 : 1000 ms    内存限制 : 32 MB
题目描述
统计所有n位数中，不包含数字0且被9整除的数的个数。
输入描述
T(T<=200)组数据
每组一行整数n(1<=n<=10000000)
输出描述
输出结果%1000000007
样例输入
2
1
2

样例输出
1
9

 
做这种题目应该这样考虑呢？

你试试,逐位取数（是0舍掉）累加起来。
根据数学：n被9整除<=>n的所有位数字和被9整除~（这样n的位数能迅速递减吧~）

你知道1亿位的能被9整除的数有多少吗

呵呵，（99……9-9……9）/9=1*10^8个
没有0的1亿位数有9^(1*10^8)个

既被9整除，又没0的数，用数学算算好了，比较复杂~要用计算机的话，非把它爆了~

[ 本帖最后由 promising 于 2010-8-9 19:31 编辑 ]

这不是不可能的，只是一般的思想是不行的，所以我问人怎么推啊，这问题能推出公式来的

先取出各个位数，再判断舍去，再计算有多少个

这样写  1秒钟判断长度为1E位的符合要求的数有多少 时间够么？

9的n次方

求9的n-1次幂，用费马小定理和欧拉定理（欧拉函数）推导。
http://zh.欧拉定理_(数论)

[ 本帖最后由 iFreeBSD 于 2010-8-10 19:25 编辑 ]