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

Z时代
2024-01-10
分类：问答

每个正整数都除以某个数字，该数字的表示（以10为底）仅包含零和一。

可以证明：

考虑数字1、11、111、1111等，最高到111 … 1，其中最后一个数字为n + 1位数字。称这些数字为m 1，m 2，…，m n +

1。每个数除以n时都有一个余数，其中两个余数必须相同。因为它们中有n + 1个，但是只有n个值可以取余数。这是著名和有用的“鸽子洞原理”的应用；

假设具有相同余数的两个数字分别为m i和m j ，而i <j。现在，从较大的值中减去较小的值。由j-i后跟i个零组成的结果数m i -m j必须是n的倍数。

但是如何找到最小的答案？和有效地？

回答：

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

#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;
}