[算法]怎么用1-9构造出前N位可以被N整除的9位数

bbbush

rt, thanks
每个数字只能使用一次
大概是 5 的数字肯定在 5 位置上
偶数肯定在偶数位置上，奇数在奇数位置上
每三位一组的数字肯定可以被 3 整除，于是中间三个数字必然是 258 或者 456，因为 258 对 3 的余数都是 2，而 456 对 3 的余数分别是 1, 2, 3

接下来需要验证的是 147,258,369 的组合，以及 123, 183, 129, 189, 327, 387, 927, 987 和 456 的组合，但是这个过程怎么用程序表示呢？

题目来源是培垠老兄，cpperl

原题目只有标题和“每个数字只能使用一次”的说明


-

herberteuler

第 4 位上只能是 2 或 6，因为如果 A3 = a1 + 10 a2 + 100 a3 是奇数，则 A3 被 4 除余 1 或 3。这样，A3 * 10 被 4 除余 2。

herberteuler

下一步，A5 = 10 A4 + 5。
A4 mod 6 可以分成两种情况：a4 = 2 或 a4 = 6。
如果 a4 = 6，则 A4 mod 6 = (10 A3 + 6) mod 6 = 0，于是 (10 A5) mod 6 = 2，所以 a6 必是 4。
如果 a4 = 2，则 A4 mod 6 = (10 A3 + 2) mod 6 = 2，于是 (10 A5) mod 6 = (100 A4 + 50) mod 6 = 250 mod 6 = 4，所以 a6 必是 2 或 8。

假设 a_k 是第 k 位上的数，而 An = A_(n-1) * 10 + an，并且 A1 = a1。

herberteuler

用类似的方法可以推知，第 7 位上只能是 1，3，或 7。

herberteuler

第 8 位上只能是 2 或 6。

herberteuler

这样，数字的形式只能是：
?8?654?2?
?4?258?6?

bbbush

可是这些怎么能写成程序呢
FP 程序员呢？

herberteuler

剩下的只有 4! * 2 = 48 种情况了，程序就好实现了吧。

herberteuler

Post by herberteuler
用类似的方法可以推知，第 7 位上只能是 1，3，或 7。

用我的推理方法，只有偶数位上的数字比较重要，奇数位上的数字只没用的。所以这个结果就可以被忽略了。

conwood

总结一下吧
1. 第5位数字是5，这个不废话了。

2. 偶数位数字是偶数，奇数位是奇数也不废话了。

3. 第123位、456位、789位组成的三个三位数都可以被3整除。

4. 考虑前4位，表示成abcd的样子，c是奇数，而ab00必然可以被4整除，那么d只能是2或者6。

5. 结合3,4，得知中间3位只能是258或者654。

6. 考虑第7,8位，由于前8位可以表示成abcd5fgh的形式，abcd5000必然可以被8整除，由5得知，f是4或者8，而400和800都可以被8整除，因此关键在7、8位，结合5的结果，知道4-8位只能是25816,25896,65432,65472

7. 789位组成的三位数可以被3整除，因此4-9位只能是258963,654327,654729,654321,654723

8. 偶数都快用光了，考虑第二位，所有可能的数字是
_4_258963
_8_654327
_8_654729
_8_654321
_8_654723

9. 下面只验证前7位对7的整除情况即可，只有10种组合了，对7整除的规律我了解不多，手工尝试也不是太大工作量。