algorithm - 查找 0 和 1 形式的倍数

Question

我试图解决http://poj.org/problem?id=1426 (2002 dhaka region) 。虽然我无法提出所需的确切算法，但由于 n 从 1 到 200 不等，我通过生成二进制数和检查可分性来预先计算所有值。现在我有一个恒定时间算法:) 但我确信这不是解决问题的正确方法。我不想使用图形搜索算法，因为这个问题属于网站的基本数学，所以我认为这个问题必须有一个数学解决方案，它不会给出 TLE。

Answer 1

这是剩下的一个简单的技巧。

必须用 0 和 1 写出每个倍数，这意味着您想要一个倍数，它是 10 的某些幂的总和，这意味着某些 {a(i)} 的 x=\sum{10^a(i)}。要找到我们想要保留的正确索引，您必须记住，作为数字 n 的倍数意味着 x mon n = 0。

所以，这就是写出 10 mod n 的幂，并找到一个总和为 0 mod n 的子集。让我们试试 19：

Num -> Num mod 19
1 -> 1
10 -> 10
10^2 -> 5
10^3 -> 12
10^4 -> 6
10^5 -> 3

现在，我们可以看到 10^1 + 10^4 + 10^5 = 19 即 0 mod 19，所以我们的解决方案是 110010 。要找到提醒 mod 19，您不必计算每个功率，只需将先前的值 mod 19 每 10 相乘，然后计算模数。

例如， 10^4 mod 10 = 10^3 * 10 mod 19 = 12*10 mod 19 = 6 ，这比计算 10^4 容易得多（也许不是小幂，但想象一下必须计算 100^100在使它成为mod 19之前）。

编辑

剩下的唯一问题是找到一个总和为 0 mod n 的子集，假设存在这样的子集。

编辑

好的，我的想法是在 n = 200 时有效，并在线性时间上解决问题。基本上，您利用总和 mod n 迟早会重叠的事实。这是真的，因为鸽子原理，但在特定情况下，只有 100 个整数，让它工作只是一个例子。无论如何，给定如前所示计算的提醒列表，您开始计算部分总和。如果你满足一个你已经拥有的值，你就有了解决方案（i-1 1 后跟 j 0）。如果您遇到提醒 0，那么您也完成了。

这是我为测试它而编写的 C# 代码：

for (int n = 2; n <= 200; n++)
{
    int[] reminder = new int[100];
    reminder[0] = 1;
    for (int i = 1; i < 100; i++)
    {
        reminder[i] = (10 * reminder[i - 1]) % n; 
    }
    var lst = reminder.Select((x, y) => new TenPower { Reminder = x, Pow = y })
        .ToList();

    bool cont = true;
    for (int i = 1; (i < 100)&&cont; i++)
    {
        if (lst[i].Reminder == 0)
        {
            cont = false;
            Console.WriteLine(n +" :: " + Math.Pow(10, lst[i].Pow));
        }
        else
        {
            lst[i].Reminder = (lst[i].Reminder + lst[i - 1].Reminder) % n;
            if (lst[i].Reminder == 0)
            {
                cont = false;
                Console.WriteLine(n + " :: " + Math.Pow(10, lst[i].Pow));
            }
            for (int j = i - 1; (j > 0) && cont; j--)
            {
                if (lst[i].Reminder == lst[j].Reminder)
                {
                    cont = false;
                    Console.Write(n + " :: ");
                    for (int k = 0; k < i - j; k++)
                    {
                        Console.Write("1");
                    }
                    for (int k = i - j-1; k < i; k++)
                    {
                        Console.Write("0");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}