项目EULER#29

Question

好吧,在通过天真​​的STL集解决了这个问题后,我正在阅读论坛条目,在那里我找到了这个条目:

 #include <iostream>   
 #include <cmath> 
 #define MAX 100
 using namespace std;

 int main(){
    int res=(MAX-1)*(MAX-1);
    for(int i=2;i<MAX;i++)
        for(int j=i*i;j<=MAX;j=j*i)
            res = res-int(MAX*(log(i)/log(j)))+1;
     cout<<res<<endl;
     return 0;
  }

作者的解释: Maximum will be 99*99. I subtracted occurrences of those numbers which are powers of some lower numbers (2-100): - For example: - 4^2,4^3,4^4 (i.e. 3 should be subtracted) as they will be duplicates from lower number powers as in 2^4,2^6,2^8

这个程序在这里给出了正确的答案检查,但是我无法得到实现的逻辑,确切地说,我没有得到重复项的确定方式.有人可以帮忙吗？

Answer 1

我可能会遗漏一些东西,但在我看来,这个程序给出了错误的答案.一个接一个.如果我设置MAX为10,那就是两个.

我读过一些玩家想要产生大致的答案,然后对Project Euler服务器进行字典攻击,以强制解决问题.其他玩家认为这反对的是事物的精神.

无论如何 - 这样的算法(从N*M开始并消除重复)是解决问题的正确方法,但正如所写,这段代码对我来说没有多大意义.请注意,在任何情况下int(MAX*(log(i)/log(j)))都对舍入误差非常敏感; 但即使你通过使用整数运算消除了这个错误源,该程序仍然给出了错误的答案.

编辑:我们如何(正确)计算重复数？

首先,你必须明白,如果两个数字具有相同的素数因子分解,则它们只是相同的.所以有仅将是复制一个₁ ^{b ₁} = 一个₂ ^{b ₂}时一个₁和一个₂是相同的整数,我将在调用不同的整数幂X.例如,

• 9 ⁷ = 3 ¹⁴ ; 这是可能的,因为9和3都是3的幂.
• 8 ⁶ = 4 ⁹ ; 这是可能的,因为8和4都是2的幂.

因此,我们已经建立了对所有重复,一个₁ = X ^{Ë ₁}和一个₂ = X ^{ë ₂}对于一些整数X,ë ₁,和ē ₁.

然后用一点代数,

a ₁ ^{b ₁} = a ₂ ^{b ₂}

x ^{e ₁ b ₁} = x ^{e ₂ b ₂}

e ₁ b ₁ = e ₂ b ₂

回到前面的例子,

• 9 ⁷ = 3 ¹⁴因为2×7 = 1×14.
• 8 ⁶ = 4 ⁹因为3×6 = 2×9.

因此,要找到任何给定的所有重复X,你只需要找到重复的简单表达EB其中2≤  X ^ë  ≤100和2≤  b  ≤100.

这是一个更简单问题的图片,x = 3和b的范围仅为2到10.我已经标记了两个有重复的地方.

e=1  a=3    *********
e=2  a=9      * * * * * * * * *
e=3  a=27       *  *  *  *  *  *  *  *  *
e=4  a=81         *   *   *   *   *   *   *   *   *
                  |               |
        1*8 = 2*4 =  4*2         3*8 = 4*6
        3^8 = 9^4 = 81^2        27^8 = 81^6

以下是重复:

e=1  a=3    *********
e=2  a=9      x x x x * * * * *
e=3  a=27       x  x  x  *  x  *  *  *  *
e=4  a=81         x   x   x   x   x   *   *   *   *

您找到的C++程序试图通过访问每对重叠的行i和j来计算它们,并计算行i与行j重叠的程度.但同样,除非我遗漏了一些东西,否则这个程序似乎无可救药.它完全错过了一些行(你从来没有i = 9和j = 27,或者i = 27和j = 81).