algorithm - 求 0 和 1 形式的倍数

Question

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

Answer 1

这是对余数的一个简单技巧。

必须用 0 和 1 来写每个倍数，这意味着您想要一个倍数，它是 10 的一些幂的总和，这意味着 x=\sum{10^a(i)} 对于一些 {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 。要找到模 19 的提醒，您不必计算每个单独的幂，只需将先前的值乘以 19 的模 19，然后计算模数即可。

例如，10^4 mod 10 = 10^3 * 10 mod 19 = 12*10 mod 19 = 6 ，这比计算 10^4 更容易(也许它不是小幂，但想象一下必须计算100^100，然后再将其修改为 19)。

编辑

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

编辑

好吧，我的想法可以达到 n = 200 并在线性时间内解决问题。基本上，您利用了 sums mod n 迟早会重叠的事实。这是真的，因为 hte pigeot 原则，但在特定情况下，只有 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();
                }
            }
        }
    }
}