这是一个关于 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;
}
如果您注意的话，变化是我将所有 xs 从 2 循环到 100，而 b 不是从 2 到 10，而是从 2 到 100。
但是，程序打印814，这是不正确的。应该是618。
任何帮助表示高度赞赏!我可能计算了两次重复，但在哪里？代码有什么问题？此外，如果您有任何有助于构建新算法的数学解释，也非常感谢!
编辑 :
我忘了提及的是，如果不是把:
for(x = 2; x <= 100; x++)我愿意:for(x = 2; x <= 6; x++)即停到 6，它打印正确的答案。而这更离奇。编辑2 :
我还要注意，对于 8 和 9(而不是 100)，它给出了正确的结果。分别为 44 和 54。
最佳答案
发现重叠数字的观察就像流程一样
首先让范围从 2 到 10 所以数字会像 22, 23, 24, 25, 26, 27, 28, 29, 210
32, 33, 34, 35, 36, 37, 38, 39, 310
42, 43, 44, 45, 46, 47, 48, 49, 410
52, 53, 54, 55, 56, 57, 58, 59, 510
62, 63, 66, 65, 66, 67, 68, 69, 610
72, 73, 77, 75, 77, 77, 78, 79, 710
82, 83, 88, 85, 88, 88, 88, 89, 810
92, 93, 94, 95, 96, 97, 99, 99, 910
102、103、104、105、106、107、108、109、1010
关键是 42 = (22)2 = 24
所以 42, 43, 44, 45, 46, 47, 48, 49, 410 将会
24、26、28、210、212、214、216、218、220
你有没有注意到，直到 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, 230
34, 36, 38, 310 , 312, 314, 316, 318, 320
102、103、104、105、106、107、108、109、1010
所以我们需要跟踪我们获得它的权力的数字，例如我们从 22 开始，数字是 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;
}
您可以为此代码添加很多增强功能，例如使用位 vector 而不是 bool 数组。
编辑:
这是对上述代码的一些解释，首先考虑从 2 到 10 的每个不同的基数。
22、23、24、25、26、27、28、29、210
24、25、28、210 , 212, 214, 216, 218, 220
26, 29, 212, 215, 218 , 221, 224, 227, 230
32, 33, 34, 35, 36, 37, 38, 39, 310
34, 36, 38, 310 , 312, 314, 316, 318, 320
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
102、103、104、105、106、107、108、109、1010
您是否注意到幂序列会为每个新碱基重复它自己，序列中的最大数字为碱基 2。
所以我们需要保存基数为 2 的结果并将其与另一个基数重用，这就是缓存的想法。
缓存中的另一件事是您需要弄清楚您有多少行以 2 为底。所以从最大底数开始，每次 10*10 除以 2 直到它变为零，但这会给你底数 2 的最大幂作为最后一行的开始，即 6 作为我们最后的 2 6 并且你开始幂次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 函数并逐个基数地进行，每个基数逐行并重用我们从缓存函数中的计算
关于python - Project Euler #29 替代解决方案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34964626/