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

Question

每个正整数除以某个数字,其表示(基数10)仅包含零和1.

人们可以证明:

考虑数字1,11,111,1111等,直到111 ... 1,其中最后一个数字有n + 1个数字.将这些数字称为m ₁,m ₂,...,m _{n + 1}.当除以n时,每个余数都有一个余数,其中两个余数必须相同.因为它们中有n + 1个,但只剩下n个值.这是着名而有用的"鸽笼原理"的应用;

假设具有相同余数的两个数字是m _i和m _j ,其中i <j.现在从较大的减去较小的.得到的数字m _i -m _j由j-i个后跟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");
    }
}

PS:OEIS中的这个序列.

Answer 2

有一个O(n)时间(算术运算mod n,真的)解决方案,它比当前接受的答案更有效.我们的想法是在顶点0..n-1上构造一个图形,其中顶点i与(i*10)%n和(i*10 + 1)%n有连接,然后使用广度优先搜索来查找按字典顺序排列的最小值路径从1到0.

def smallest(n):
    parents = {}
    queue = [(1 % n, 1, None)]
    i = 0
    while i < len(queue):
        residue, digit, parent = queue[i]
        i += 1
        if residue in parents:
            continue
        if residue == 0:
            answer = []
            while True:
                answer.append(str(digit))
                if parent is None:
                    answer.reverse()
                    return ''.join(answer)
                digit, parent = parents[parent]
        parents[residue] = (digit, parent)
        for digit in (0, 1):
            queue.append(((residue * 10 + digit) % n, digit, residue))
    return None

Answer 3

好问题。我使用BFS通过中间相遇和其他一些修剪来解决此问题。现在，我的代码可以在合理的时间内解决n <10 ⁹。

#include <cstdio>
#include <cstring>

class BIT {
private: int x[40000000];
public:
    void clear() {memset(x, 0, sizeof(x));}
    void setz(int p, int z) {x[p>>5]=z?(x[p>>5]|(1<<(p&31))):(x[p>>5]&~(1<<(p&31)));}
    int bit(int p) {return x[p>>5]>>(p&31)&1;}
} bp, bq;

class UNIT {
private: int x[3];
public: int len, sum;
    void setz(int z) {x[len>>5]=z?(x[len>>5]|(1<<(len&31))):(x[len>>5]&~(1<<(len&31)));}
    int bit(int p) {return x[p>>5]>>(p&31)&1;}
} u;

class MYQUEUE {
private: UNIT x[5000000]; int h, t;
public:
    void clear() {h = t = 0;}
    bool empty() {return h == t;}
    UNIT front() {return x[h];}
    void pop() {h = (h + 1) % 5000000;}
    void push(UNIT tp) {x[t] = tp; t = (t + 1) % 5000000;}
} p, q;

int n, md[100];

void bfs()
{
    for (int i = 0, tp = 1; i < 200; i++) tp = 10LL * (md[i] = tp) % n;

    u.len = -1; u.sum = 0; q.clear(); q.push(u); bq.clear();
    while (1)
    {
        u = q.front(); if (u.len >= 40) break; q.pop();
        u.len++; u.setz(0); q.push(u);
        u.setz(1); u.sum = (u.sum + md[u.len]) % n;
        if (!bq.bit(u.sum)) {bq.setz(u.sum, 1); q.push(u);}
        if (!u.sum) {
            for (int k = u.len; k >= 0; k--) printf("%d", u.bit(k));
            puts(""); return;
        }
    }

    u.len = 40; u.sum = 0; p.clear(); p.push(u); bp.clear();
    while (1)
    {
        u = p.front(); p.pop();
        u.len++; u.setz(0); p.push(u);
        u.setz(1); u.sum = (u.sum + md[u.len]) % n;
        if (!bp.bit(u.sum)) {bp.setz(u.sum, 1); p.push(u);}
        int bf = (n - u.sum) % n;
        if (bq.bit(bf)) {
            for (int k = u.len; k > 40; k--) printf("%d", u.bit(k));
            while (!q.empty())
            {
                u = q.front(); if (u.sum == bf) break; q.pop();
            }
            for (int k = 40; k >= 0; k--) printf("%d", u.bit(k));
            puts(""); return;
        }
    }
}

int main(void)
{
    // 0 < n < 10^9
    while (~scanf("%d", &n)) bfs();
    return 0;
}