如何判读一个数的倍数全有8组成

gxqcn

不用大数运算，在 n 是一个常规整数时。
因为中途即用模运算，而不是算完了再取模。
你可以先学习一下初等数论。

troy

谢谢啊！差不多会了！

troy

原帖由 gxqcn 于 2008-9-29 15:15 发表
不用大数运算，在 n 是一个常规整数时。
因为中途即用模运算，而不是算完了再取模。
你可以先学习一下初等数论。

求一个数所有因子的时候，有什么好方法可以加快速度？

另外发现n=3的时候，公式不适用！

gxqcn

我在回老家途中车上就注意到了楼上最后一句的问题，
可惜无法上网修正。

X = 88...8(x个8) = 8/9 * (10^x - 1)

所以 n|X 与否，不仅要考虑分子的贡献，还要考虑分母的约束。

修正的解答版本如下：

Input ：正整数 n，
Output：最小的x，使得x个“8”可被n整除（若不存在，返回x=0）
算法：
1、if (n|8) then return x=1;
2、if (2|n or 5|n) then return x=0;
3、计算：x=10对模n的指数（方法见2#）；
4、if (3|n and 3∤x) then x=x*3;
5、if (9|n and 9∤x) then x=x*3;
6、return x;