algorithm - 如何找到除以给定数字的只有 0 和 1 的最小数字？

Question

每个正整数除以某个数字，该数字的表示形式(以 10 为底)仅包含零和一。

可以证明:

考虑数字 1、11、111、1111 等直到 111...1，其中 最后一个数字有 n+1 位。称这些数字为 m₁、m₂、...、m_n+1。每个都有一个 除以 n 的余数，并且其中两个余数必须相同。 因为它们有 n+1 个，但余数只能取 n 个值。 这是著名且有用的“鸽巢原理”的应用；

假设余数相同的两个数是m_i和m_j ，我 < j。现在从较大的中减去较小的。结果数 m_i−m_j 由 j - i 个 1 后跟 i 个零组成，必须是 n 的倍数。

但是如何找到最小的答案呢？并且高效？

Answer 1

这道题等于用10ⁱ mod n(对于每个i，最多可以用一次)得到n的和m。这就像背包问题或子集和问题。这样，动态规划将完成任务。

在动态规划中，复杂度是O(k*n)。 k 是答案中的位数。对于 n<10⁵，此代码完美运行。

代码:

#include <stdio.h>
#define NUM 2000

int main(int argc, char* argv[])
{
    signed long pow[NUM],val[NUM],x,num,ten;
    int i,j,count;
    for(num=2; num<NUM; num++)
    {
        for(i=0; i<NUM; pow[i++]=0);
        count=0;
        for(ten=1,x=1; x<NUM; x++)
        {
            val[x]=ten;

            for(j=0; j<NUM; j++)if(pow[j]&&!pow[(j+ten)%num]&&pow[j]!=x)pow[(j+ten)%num]=x;
            if(!pow[ten])pow[ten]=x;
            ten=(10*ten)%num;
            if(pow[0])break;
        }

        x=num;
        printf("%ld\tdivides\t",x=num);
        if(pow[0])
        {
            while(x)
            {
                while(--count>pow[x%num]-1)printf("0");
                count=pow[x%num]-1;
                printf("1");
                x=(num+x-val[pow[x%num]])%num;
            }
            while(count-->0)printf("0");
        }
        printf("\n");
    }
}

附言: OEIS 中的此序列.