找符合条件的整数 - 编程之美2.8

任意给定一个正整数N，求一个最小的正整数M（M >1），使得N * M 的十进制表示形式里只含有1 和0，例如：

1 * 1 = 1 2 * 5 = 10
3 * 37 = 111 4 * 25 = 100
5 * 2 = 10 6 * 185 = 1,110
7 * 143 = 1,001 8 * 125 = 1,000
9 * 12,345,679 = 111,111,111

http://blog.csdn.net/jcwkyl/article/details/3859155
方法四：对方法三的改进。将方法三的搜索空间按模N余数分类，使得搜索时间和空间都由原来的指数级降到了O(N)。改进的原理：假设当前正在搜索由0，1组成的K位十进制数，这样的K位十进制数共有2^k个。假设其中有两个数X、Y，它们模N同余，那么在搜索由0、1组成的K+1位十进制数时，X和Y会被扩展出四个数：10X, 10X+1, 10Y, 10Y+1。因为X和Y同余（同余完全可以看作相等），所以10X与10Y同余，10X+1与10Y+1同余。也就是说由Y扩展出来的子树和由X扩展产生出来的子树产生完全相同的余数，如果X比Y小，那么Y肯定不是满足要求的最小的数，所以Y这棵子树可以被剪掉。这样，2^K个数按照模N余数分类，每类中只保留最小的那个数以供扩展。原来在这一层需要搜索2^K个数，现在只需要搜索O(N)个数。例如，当N=9时，第0层是1(1)，

如上图所示，第2层的110，第三层的1010、1110都因为同一层有和它同余且更小的数而被剪掉。如果按照方法三搜索，第三层本来应该有8个结点，但现在只有4个结点。

1. // 解法四：将搜索空间分过类的广度搜索，这样空间占用是O(N)而不是  
2. // 指数级。分类的原则是按照模N的余数分类
3. struct QNode {  
4.     int v, r; // v is value, r is remainder  
5.     QNode(int vv, int rr): v(vv), r(rr) {}  
6.     QNode(): v(0), r(0) {}  
7. };  
8. int main() {  
9.     int N;  
10.     while(scanf("%d", &N) != EOF) {  
11.         //bitset<N> bn;  
12.         queue<QNode> q;  
13.         q.push(QNode(1, 1));  
14.         while(!q.empty()) {  
15.             //bn.reset();  
16.             vector<bool> bn(N, false);  
17.             int s = q.size();  
18.             while(s--) {  
19.                 QNode t = q.front();  
20.                 if(t.r == 0) {  
21.                     printf("n = %d, m = %d, n*m = %d/n", N, t.v/N, t.v);  
22.                     goto ok;  
23.                 }  
24.                 q.pop();  
25.                 if(!bn[t.r * 10 % N]) {  
26.                     bn[t.r * 10 % N] = true;  
27.                     q.push(QNode(t.v * 10, t.r * 10 % N));  
28.                 }  
29.                 if(!bn[(t.r * 10 + 1) % N]) {  
30.                     bn[(t.r * 10 + 1) % N] = true;  
31.                     q.push(QNode(t.v * 10 + 1, (t.r * 10 + 1) % N));  
32.                 }  
33.             }  
34.         }  
35. ok:;  
36.     }  
37.     return 0;  
38. }  

方法三：因为N*M的取值就是1,10,11,100,101,110,111,......所以直接在这个空间搜索，这是对方法一的改进。搜索这个序列直到找到一个能被N整除的数，它就是N*M，然后可计算出M。例如N=3时，搜索树如下：

上图中括号内表示模3的余数。括号外表示被搜索的数。左子树表示0，右子树表示1.上图中搜索到第二层（根是第0层）时遇到111，它模3余数为0.所以N*M=111, M=111/3=37。

1. // 解法三(1):广度优先搜索  
2. int main() {  
3.     int N;  
4.     while(scanf("%d", &N) != EOF) {  
5.         queue<int> q;  
6.         q.push(1);  
7.         while(!q.empty()) {  
8.             int t = q.front();  
9.             q.pop();  
10.             if(t % N == 0) {  
11.                 printf("n = %d, m = %d, n*m = %d/n", N, t/N, t);  
12.                 break;  
13.             }  
14.             q.push(t * 10);  
15.             q.push(t * 10 + 1);  
16.         }  
17.     }  
18.     return 0;  
19. }  

方法一：给定N，令M从2开始，枚举M的值直到遇到一个M使得N*M的十进制表示中只有1和0.

1. int HasOnlyOneAndZero(unsigned int n) {  
2.     while(n) {  
3.         if(n % 10 >= 2) return 0;  
4.         n /= 10;  
5.     }  
6.     return 1;  
7. }  
8. int main() {  
9.     int n, m;  
10.     while(scanf("%d", &n) != EOF) {  
11.         for(m = 1;;m++) {  
12.             if(HasOnlyOneAndZero(n*m)) {  
13.                 printf("n = %d, m = %d, n*m = %d/n", n, m, n*m);  
14.                 break;  
15.             }  
16.         }  
17.     }  
18.     return 0;  
19. }  

方法二：求出10的次方序列模N的余数序列并找出循环节。然后搜索这个余数序列，搜索的目的就是要在这个余数序列中找到一些数出来让它们的和是N的倍数。例如N=13，这个序列就是1,10,9,12,3,4然后不断循环。很明显有1+12=13，而1是10的0次方，12是10的3次方，所以这个数就是1000+1=1001，M就是1001/13=77。


符合条件整数存在的证明
http://blog.csdn.net/cjl19880906/article/details/8441365
现在要讨论和证明的是存在这样的整数X，使得X%N=0。

因为 数列

      （1）

是一个无穷数列并且数列中的每一项的取值范围都在【0，N-1】。

这样的话，考虑鸽巢原理，肯定存在第 s，t 项使得10^s = 10^t  (mod N)。

再由模运算的性质：

若a≡b (mod p)，则对于任意的c，都有ac≡ bc (mod p) 

可以知道数列（1）中存在循环节，节长 s-t 。比如，若是N=13，那么这个数列是1,10,9,12,3,4，1,10,9,12,3,4，1,10,9,12,3,4，1,10,9,12,3,4... ...

于是有

所以

这就找到了一个符合条件的X。因为最终要求最小的一个符合条件的整数，既然存在了一个这样的整数，自然的最小的肯定存在了。

http://gpww.blog.163.com/blog/static/11826816420099782740350/\

解法二

    我们也可以反过来考虑，去遍历乘数，例如，当N=13 时，采用“试乘”的办法去得到M——13 的个位数是3，能够让3 变成1 的数只有7（3×7＝21），依次类推：

    需要注意的是，个位不可以“试乘”0，因为这样得到的M 不是最小的（还可以缩小10 倍），其它高位都可以“试乘0。

    另外，还可能出现无限循环的“试乘”：

    当N 为d 位数的时候，“试乘”可能会出现d 位循环出现，需要排除，关键代码如下：

        void Find_01_Format(BigInt x, BigInt y, BigInt z, int digit, Dictionary<string> cycleDic)
        {
            for (int m = digit > 0 ? 0 : 1; m < 10; m++)
            {
                var sum = m * x[0] + z[digit];
                var u = sum % 10;
                if (u == 1 || u == 0)//找到一个能将最后乘积digit 位变为0 或1 的数
                  {
                    y[digit] = m;
                    var p = (x * m).LeftShift(digit).Add(z);
                    if (min.Digit > 0 && p >= min) continue;//大于当前最小值，剪枝
                       //<检查是否找到结果> <检查是否出现循环>
                    Find_01_Format(x, y.Clone(), p, digit + 1, copyDic);
                }
            }
        }

其中：
x 是被乘数，y 是乘数，z 是乘积
digit 是当前“试乘”的位数
cycleDic 是用于判断是否出现循环的哈希表
BigInt. LeftShift(k)是将10 进制数左移k 位，等价于×10k
BigInt.Add(n)是将本数字加上n 后返回自身。
min 保存的当前搜索到的最小的z

解法三

    当N 比较大的时候，两种方法都比较慢，例如N=987654 时：987654 * 1,113,861,738,118,815 = 1,100,110,001,100,000,110,010

    能否在秒级解决10 万以下的数呢？
    可以这样考虑，我们要得到的乘积只包含0 和1，即：
    z = b1 * 10^0 + b2 * 10^1 + b3 * 10^2 + … + bk * 10^k-1
    其中，bi = 0 或1，i = 1，2，3，…，k
    考虑无穷数列：10^0 % N，10^1 % N，10^2 % N，…，由于N 的余数总是< N，所以这个数列必将存在循环节，例如，当N = 13 时，此数列为：

1, 10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1, 10…

    现在问题就可以转化为：在这个无穷数列中，挑选一些数出来，使得他们的和能够整除N，一种挑选方案实际上对应于b1 b2 b3…的一种真值指派（每一位选中为1，否则为0）。
   

    到此我们已经发现，这个问题可以采用“分级组合法”：
    给定无穷序列100 % N，101 % N，102 % N，…求1～n 级的情况。第i 级保存序列中i 个数相加所能得到和，直到找到最小的一个和能够整除N。

    代码如下：

           var heap = new List<SumSet>(); // SumSet 类保存数列中n 个数相加所能得到的和
             heap.Add(new SumSet());
            heap[0].Add(0);
            int d = 1, b = 1, s = 0, cycleStart = -1;
            SumSet.Sum min = null;
            while (true)
            {
                var r = b % n;
                //找到循环节开始的那个元素
                 if (cycleStart < 0 && heap.Count > 1 && heap[1].ContainsKey(r)) cycleStart = r;
               if (r == cycleStart) s++; //进入下一个循环周期，前s 级不需要再扩展
                 bool found = false;
                heap.Add(new SumSet());
                for (int lvl = d - 1; lvl >= s; lvl--)
                    foreach (var sum in heap[lvl])
                    {
                        var newSum = sum.Add(r, d - 1);
                        if (newSum.value % n == 0)
                        {
                            found = true;
                            if (min == null || newSum < min) min = newSum;
                        }
                        heap[lvl + 1].Renew(newSum);
                    }
                if (found) break;
                b *= 10 % n;
                b %= n;
                d++;
            }

其中：
n 是给定的数字N
d 表示当前计算到无穷数列的哪一位
b 依次是10^0，10^1，10^2，10^3…，为了防止越界，计算过程中先求余，结果不变。

讨论

    通过“分级组合法”基本能够秒级解决10 万以下的数字了，逐数测试时，相比前面两法“卡卡”，真可谓酣畅淋漓！
    由于从下往上看每级元素数量列呈现“橄榄型”——中间多两头少，在面对更大的数字的时候，未能到达此数字之前，就被困扰大量计算中，类似“广度优先搜索”。那么在需要计算这么大的数字之前，还可以改进此算法，利用“深度优先搜索”、“启发式搜索”，或者遗传算法给出近似解。

《编程之美》2.8 扩展问题
http://icyxiangzi.blog.163.com/blog/static/169778905201010279208345/
5、扩展问题2
使得N*M只含有0和1，并且N*M<2^16,N*M<=11111，且使得M尽可能的大。首先，用11111%N，观察余数是否为0。如果余数为0，那么11111/N就是所求的M。如果余数不是0，设余数是a，与原题一样，求一个最小的由0和1组成的数b，使得b模N等于a，然后用(11111-b)/N就是所求的M。

http://blog.csdn.net/zhanglei0107/article/details/8277949
http://hi.baidu.com/silverxinger/item/50e87c13259dfceb5f53b1a5