如何找到的最小数与仅有0和1，它是由一个给定的数量除以？ [英] How to find the smallest number with just 0 and 1 which is divided by a given number?

问题描述

每一个正整数除以一些数字，其重presentation（基数为10）只包含零和一。

Every positive integer divide some number whose representation (base 10) contains only zeroes and ones.

我们可以证明：

考虑数字1，11，111，1111，等高达111 ... 1，其中的 最后一个数字有n + 1个数字。把这些数m <子> 1 ，男 ₂ ，...，M <子> N + 1 。每个人都有一个 余时除以n，和其中的两个余数必须是相同的。 因为有n其中+ 1，但仅N个值的余数可以采取。 这就是著名的和有用的鸽巢原理的申请;

Consider the numbers 1, 11, 111, 1111, etc. up to 111... 1, where the last number has n+1 digits. Call these numbers m₁, m₂, ... , m_n+1. Each has a remainder when divided by n, and two of these remainders must be the same. Because there are n+1 of them but only n values a remainder can take. This is an application of the famous and useful "pigeonhole principle";

假设这两个数字与同余m个<子>我和M <子>Ĵ 与I＆LT;学家现在从较大减去较小。由此产生的数m <子>我 -m <子>Ĵ，包括歼 - 我的人跟着我零，必须是n的倍数

Suppose the two numbers with the same remainder are m_i and m_j , with i < j. Now subtract the smaller from the larger. The resulting number, m_i−m_j, consisting of j - i ones followed by i zeroes, must be a multiple of n.

但如何找到最小的答案？并有效牙缝？

But how to find the smallest answer? and effciently?

推荐答案

有趣的问题。我使用BFS来解决这个问题，有相遇中间人和其他一些剪枝。现在我的code可以解决N'LT; 10 ⁹ 在合理的时间

Nice question. I use BFS to solve this question with meet-in-the-middle and some other prunings. Now my code can solve n<10⁹ in a reasonable time.

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

这篇关于如何找到的最小数与仅有0和1，它是由一个给定的数量除以？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！