Project Euler #29 替代解决方案

Question

这是一个关于 Project Euler 问题的问题。您可以在这里找到问题的描述：https : //projecteuler.net/problem=29

好的，首先，让我澄清一下，我已经解决了这个问题，我只是在寻找更多基于数学的替代解决方案。
其次，为了不让没有解决的人破坏问题，如果你没有解决，请不要继续。:)

因此，我使用 Python 解决了这个问题，并且因为它支持大数字和列表推导式，所以我能够想出一个单行代码：

print(len(set([a ** b for a in range(2, 101) for b in range(2, 101)])))

现在，我试图通过使用更多的数学知识（C 本身不支持大数字或列表推导式）在 C 中解决它。我遇到了这个线程：PROJECT EULER #29，其中接受的答案给了我一些想法，我想出了这个代码：

int main(void) {

    int found[1000];    // an array where I hold the found values(0 or 1)
    int e, b, i, count, x;

    count = 0;     // number of duplicates
    x = 3;
    for(i = 0; i < 1000; i++)
         found[i] = 0;


    for(e = 1; (int)pow(x, e) <= 100; e++) {
        for(b = 2; b <= 10; b++) {
            if(found[e * b])    // if the value has been found, then we have duplicate
                count++;
            found[e * b] = 1;   // mark that we found the value
        }
    }

    printf("count: %d\n", count);

    return 0;
}

使用此代码，我正在执行您在上面答案底部看到的操作，根据他之前的解释，他展示了一些关于如何找到 x = 3 的重复项的图表。我正在尝试做同样的事情。现在，如果您运行我的代码，它会根据上述答案的图表正确输出 13，即重复的数量。

所以，我试图扩展它来解决实际的项目欧拉问题，因为如果我能够找到重复的数量，那么我将从数字 99 * 99 中减去它（这是可能的幂组合，因为 2 <= a <= 100 and 2 <= b <= 100) 这就是答案。结果是：

int main(void) {

    int found[1000];
    int e, b, i, count, x;

    count = 0;
    for(x = 2; x <= 100; x++) {
        for(i = 0; i < 1000; i++)
             found[i] = 0;


        for(e = 1; (int)pow(x, e) <= 100; e++) {
            for(b = 2; b <= 100; b++) {
                if(found[e * b])
                    count++;
                found[e * b] = 1;
            }
        }
    }

    printf("count: %d\n", count);

    return 0;
}

如果你注意的话，变化是我循环了所有从 2 到 100 的 xs，而 b 不是从 2 到 10 而是从 2 到 100。
但是，程序打印了 814，这是不正确的。应该是 618。非常感谢任何帮助！我可能计算了两次重复，但在哪里？代码有什么问题？此外，如果您有任何有助于构建新算法的数学解释，也非常感谢！

编辑：
我忘记提及的是，如果不是放置：
for(x = 2; x <= 100; x++) 我做：
for(x = 2; x <= 6; x++)
即停止到 6，它会打印正确的答案。而这更离奇。

EDIT2：
我还要注意，对于 8 和 9（而不是 100），它给出了正确的结果。分别为 44 和 54。

Answer 1

寻找重叠数字的观察是作为流程
首先让范围从 2 到 10所以数字将像
2 ² , 2 ³ , 2 ⁴ , 2 ⁵ , 2 ⁶ , 2 ⁷ , 2 ⁸ , 2 ⁹ , 2 ¹⁰
3 ² 3 ³ 3 ⁴ 3 ⁵ 3 ⁶ 3 ⁷ 3 ⁸ 3 ⁹ 3 ¹⁰
4 ² 4 ³ 4 ⁴ 4 ⁵ 4⁶，4 ⁷，4 ⁸，4 ⁹ 4 ¹⁰
5 ²，5 ³，5 ⁴，5 ⁵ 5 ⁶ 5 ⁷，5 ⁸ 5 ⁹ 5 ¹⁰
6 ²，6 ³，6 ⁶ 6 ⁵ , 6 ⁶ , 6 ⁷ , 6 ⁸ , 6 ⁹ , 6 ¹⁰
7 ² , 7 ³ , 7 ⁷ , 7 ⁵ , 7 ⁷ , 7 ⁷, 7 ⁸ , 7 ⁹ , 7 ¹⁰
8 ² , 8 ³ , 8 ⁸ , 8 ⁵ , 8 ⁸ , 8 ⁸ , 8 ⁸ , 8 ⁹ , 8 ¹⁰
9 ² , 9 ³ , 9 ⁴ , 9 ⁶ , 9 ⁵ , 9 ⁷ 9 ⁹ 9 ⁹ 9 ¹⁰
10 ² 10 ³ 10 ⁴ 10 ⁵ 10 ⁶ 10 ⁷ 10 ⁸，10 ⁹，10 ¹⁰
的关键点是4 ² =（2 ²）² = 2 ⁴ ，以便
4 ²，4 ³，4 ⁴，4 ⁵，4 ⁶，4 ⁷，4 ⁸，4 ⁹ 4 ¹⁰ 将 2 ⁴ , 2 ⁶ , 2 ⁸ , 2 ¹⁰ , 2 ¹² , 2 ¹⁴ , 2 ¹⁶ , 2 ¹⁸ , 2 ²⁰
你有没有注意到直到2¹⁰我们仍然有重复的数字，之后我们开始有一个新数字，
所以使用这个观察重写上面的数字，它将是
2 ² , 2 ³ , 2 ⁴ , 2 ⁵ , 2 ⁶ , 2 ⁷ , 2 ⁸ , 2 ⁹ , 2 ¹⁰
3 ² , 3 ³ , 3 ⁴ , 3 ⁵ , 3 ⁶ , 3 ⁷ , 3 ⁸ , 3 ⁹ , 3 ¹⁰
2 ⁴ , 2 ⁵ , 2 ⁸ , 2 ¹⁰ , 2¹²，2 ¹⁴，2 ¹⁶，2 ¹⁸，2 ²⁰
5 ²，5 ³，5 ⁴，5 ⁵ 5 ⁶ 5 ⁷，5 ⁸ 5 ⁹ 5 ¹⁰
6 ²，6 ³，6 ⁴，6 ⁵ , 6 ⁶ , 6 ⁷ , 6 ⁸ , 6 ⁹ , 6 ¹⁰
7 ² , 7 ³ , 7 ⁴ , 7 ⁵ , 7 ⁶ , 7 ⁷，7 ⁸ 7 ⁹ 7 ¹⁰
2 ⁶，2 ⁹，2 ¹²， 2 ¹⁵，2 ¹⁸，2 ²¹，2 ²⁴，2 ²⁷，2 ³⁰
3 ⁴，3 ⁶，3 ⁸，3 ¹⁰，3 ¹²， 3 ¹⁴ , 3 ¹⁶ , 3 ¹⁸ , 3 ²⁰
10 ² , 10 ³ , 10 ⁴ , 10 ⁵ , 10 ⁶ , 10 ⁷, 10 ⁸ , 10 ⁹ , 10 ¹⁰
所以我们需要跟踪我们得到它的幂的数字，例如我们从 2 ²开始，数字是 2，幂是 2 增加功率的差距是 1。它的代码是：

vector<int>  calcCache(int rangeStart, int rangeEnd)
{
    int maxBase = rangeEnd*rangeEnd;
    int maxStartPow = 1;
    while (maxBase > 0)
    {
        maxBase /= 2;
        maxStartPow++;
    }
    maxStartPow /= 2;
    vector<bool> seen(maxStartPow*rangeEnd, false);
    int i = rangeStart;
    vector<int> cahce;


    int maxprev = 0;

    int gap = 1;
    int startpow = 2 * gap;
    int j = pow(i, startpow);

    int diff = rangeEnd - rangeStart;
    int maxCurrent = diff*gap + startpow;

    while (j <= rangeEnd*rangeEnd)
    {

        int currPow = startpow;
        int k = 0;
        int currRes = 0;
        while (k <= diff)
        {

            if (!seen[currPow])
            {
                currRes++;
            }
            seen[currPow] = true;
            currPow += gap;
            k++;
        }
        cahce.push_back(currRes);

        maxprev = currPow - gap;


        gap++;
        startpow = 2 * gap;
        j = pow(i, startpow);
    }

    return cahce;
}
int distinctpowers(int rangeStart, int rangeEnd)
{
    vector<bool> arr(rangeEnd*rangeEnd + 1, false);
    int res = 0;

    vector<int> cache = calcCache(rangeStart, rangeEnd);
    for (int i = rangeStart; i <= rangeEnd; i++)
    {

        if (!arr[i*i])
        {
            int maxprev = 0;

            int gap = 1;
            int startpow = 2 * gap;
            int j = pow(i, startpow);

            int diff = rangeEnd - rangeStart;
            int maxCurrent = diff*gap + startpow;

            while (j <= rangeEnd*rangeEnd)
            {

                int currPow = startpow;
                res += cache[gap - 1];

                maxprev = currPow - gap;
                arr[j] = true;

                gap++;
                startpow = 2 * gap;
                j = pow(i, startpow);


            }
        }
    }
    return res;
}

您可以为此代码添加很多增强功能，例如使用位向量而不是 bool 数组。

编辑：

这是对上述代码的一些解释，首先考虑从 2 到 10 的每个不同的基数。
2 ² , 2 ³ , 2 ⁴ , 2 ⁵ , 2 ⁶ , 2 ⁷ , 2 ⁸ , 2 ⁹ , 2 ¹⁰
2 ⁴ , 2 ⁵ , 2 ⁸ , 2 ¹⁰ , 2 ¹² , 2 ¹⁴ , 2 ¹⁶ , 2 ¹⁸ , 2 ²⁰
2 ⁶ , 2 ⁹ , 2 ¹² , 2 ¹⁵ , 2 ¹⁸ , 2²¹ 2 ²⁴ 2 ²⁷ 2 ³⁰

3 ²，3 ³，3 ⁴，3 ⁵，3 ⁶，3 ⁷，3 ⁸，3 ⁹，3 ¹⁰
3 ⁴，3 ⁶，3 ⁸，3 ¹⁰，3 ¹²，3 ¹⁴，3 ¹⁶，3 ¹⁸， 3 ²⁰

5 ² , 5 ³ , 5 ⁴ , 5 ⁵ , 5 ⁶ , 5 ⁷ , 5 ⁸ , 5 ⁹ , 5 ¹⁰

6 ² , 6 ³ , 6 ⁴ , 6 ⁵ , 6 ⁶ , 6 ⁷ , 6 ⁸ , 6 ⁹ , 6 ¹⁰

7 ² 7 ³ 7 ⁴ 7 ⁵ 7 ⁶ 7 ⁷ 7 ⁸ 7 ⁹ 7 ¹⁰

10 ² , 10 ³ , 10 ⁴ , 10 ⁵ , 10 ⁶ , 10 ⁷ , 10 ⁸ , 10 ⁹ , 10 ¹⁰

您是否注意到幂序列会为每个新基重复它自己，序列中的最大数字为基 2。
所以我们需要保存基 2 的结果并将其与另一个基重用，这就是缓存的想法。
缓存中的另一件事是您需要弄清楚您有多少行以 2 为底。所以从最大底数开始，每次 10*10 除以 2 直到它变为零，但这会给你底数 2 的最大幂作为最后一行的开始，即 6 作为我们最后的 2 ⁶并且你从2 到 6 每行增加 2，所以我们需要将结果除以 2

int maxBase = rangeEnd*rangeEnd;
int maxStartPow = 1;
while (maxBase > 0)
{
    maxBase /= 2;
    maxStartPow++;
}
maxStartPow /= 2;

之后，我们需要跟踪我们看到的权力，您可以遇到的最大权力是 maxStartPow*rangeEnd。

vector<bool> seen(maxStartPow*rangeEnd, false);

然后我们开始在我们的基础中逐行进行，在这种情况下为 2，每条线记住我们看到的权力，当我们看到新的权力时，我们增加这条线的结果。
这段代码最重要的部分是，在计算每一行之后，我们需要存储它，因为我们将在我们的主要问题中重用它。

int maxprev = 0;

int gap = 1;
int startpow = 2 * gap;
int j = pow(i, startpow);

int diff = rangeEnd - rangeStart;
int maxCurrent = diff*gap + startpow;

while (j <= rangeEnd*rangeEnd)
{

    int currPow = startpow;
    int k = 0;
    int currRes = 0;
    while (k <= diff)
    {

        if (!seen[currPow])
        {
            currRes++;
        }
        seen[currPow] = true;
        currPow += gap;
        k++;
    }
    cahce.push_back(currRes);

    maxprev = currPow - gap;


    gap++;
    startpow = 2 * gap;
    j = pow(i, startpow);
}

之后我们回到我们的 distinictPowers 函数并逐个基础地进行，每个基础逐行并重用我们从缓存函数中的计算