一道acm题 不知道怎么做，求算法
一道acm题：
1到n，n不超10的12次方，一个数能被它的各位和整除，在[1,n]这样的数有多少个。
比如说12就能被它的各位和整除，因为1+2=3，12/3=4；
输入n的值
测试样例：
100
输出
33
运行要在1000ms之内完成，这题这么做啊。各位帮忙看看！谢谢！！
[解决办法]
1---10都可以
12 18 20 21 24 27 30 36 40 45 48 50 54 。。。。
可以发现后面加0的都可以
那么先把这部分加起来
1 10 100 1000 10000 100000 1000000......
2 20 200 2000 20000 200000 3000000......
...
9 90 900 9000 90000 900000 9000000......
剩下的有一个规律，起码都是3的倍数，是3的倍数不一定满足条件，但是满足条件一定是3的倍数
[解决办法]
我的一点想法：
由于数据范围巨大，所以可以用字符串表示数值(用数码倒序表示)，这样在计算各位和的时候也很方便
至于判断是否整除，就考虑相同数码排列而成的数是否满足条件(此时他们的各位和都是相同的)，再计算其排练组合的个数
这样做在时间上要优化不少吧
[解决办法]
一个数若能其各位上的和整除，则其必须有因子，且其因子最大不能超过12*9=108，所以满足条件的数必须是i([2,128])的倍数，可以从i的1倍，2倍，。。。去找，能省掉很多质因子，或因子比较大的整数。
ps：具体的还没想清楚，lz可以参考下
[解决办法]
应该存在同余的规律： 该数的各位数之和与该数本身对9同余。
