Euler项目29替代方案

Question

这是一个关于projecteuler问题的问题。 您可以在这里找到问题的描述：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在这里，接受的答案给了我一些想法，我想出了以下代码：

^{pr2}$

有了这段代码，我正在做你能看到答案底部的东西 上面，他展示了一些关于如何找到重复项的图表 x=3，根据他之前的解释。我也在试着做同样的事情。现在，如果你运行我的代码， 根据上述答案的图表，它正确地输出13，即重复数。

所以，我试图扩展它来解决实际的ProjectEuler问题，因为如果我能找到重复的数量，那么我将从数字99*99中减去它（这是可能的幂组合，因为2<；=a<；=100和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的x，而b不是从2到10，而是从2到100。
但是，程序打印814，这是不正确的。应该是618。 非常感谢任何帮助！我可能数了两次重复数，但在哪里呢？密码怎么了？另外，如果你有任何数学解释，有助于建立一个新的算法，这也是高度赞赏！在

编辑：
我忘了提的是，如果不是把：
for(x = 2; x <= 100; x++) 我知道：
for(x = 2; x <= 6; x++)
i、 停到6，它会打印出正确的答案。更奇怪的是。在

编辑2：
我还要指出，对于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¹⁰
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^{10<2><2><2>2，sup> 你有没有注意到，直到210我们仍然有重复的数字，之后我们开始有一个新的数字
所以用这个观察改写上面的数字，它将是
22、23、24、25、26、27、28、29、210
32，33，34，35，36，37，38，39，310
24、25、28、210、212、214、216、218、220
52，53，54，55，56，57，58，59，510
62，63，64，65，66，67，68，69，610
72、73、74、75、76、77、78、79、710
26，29，212，215，218，221，224，227，23034，36，38，310，312，314，316，318，320
102，103，104，105，106，107，108，109，1010
所以我们需要跟踪这个数，我们得到它的幂，例如我们从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的幂序列中的数字最多。
所以我们需要将结果保存为base2，并在另一个base中重用它，这就是缓存的思想。
缓存中还有一件事是，您需要计算出有多少行是以2为基数的。所以从最大基数开始，每次10*10除以2，直到它变为零，但是这将给你基数2的最大幂，作为最后一行的开始，6作为最后2⁶，从2到6的幂每行增加2，所以我们需要将结果除以2

^{pr2}$

我们需要的是最大的能量来维持你的轨道。在

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

然后我们开始在基线中逐行计算，在这个例子中，每一行都会记住我们看到的幂次，当我们看到新的幂次时，我们会增加这条线的结果。
这段代码最重要的部分是，在计算完每一行之后，我们需要存储它，因为我们将在主要问题中重用它。在

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函数，逐基进行，每个基逐行执行，并重用缓存函数中的计算