项目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

(至少)有两种方法来解决这个问题。一种方法是从0开始计算不同的值，并为以前从未见过的每个计算值添加一个。另一种方法是计算值的最大值，然后对每个重复减去一个。

这张海报正在尝试第二种方法。对于99个值，a可以从2到100不等，b也是如此，因此产生的值为99 * 99。然后，海报试图减去重复的值，以得到正确的答案。

编辑:然而，海报写了一个不正确的算法。例如，设置MAX = 8或9。对于8，它应该给出44，但是它给了45。对于9，它应该给出54，但是给出56。要么他们幸运地发现了一种对某些输入给出正确答案的算法，要么他们反向设计了一种在MAX = 100时起作用的算法，而不是所有其他值。

Answer 2

这个问题涉及到如何将从一个范围中选择的两个数字组合起来。有99个可能的数字，所以组合的数目是99 * 99，可能是重复的。他在这里的基本算法是计算出存在多少个重复，并从最大值中减去这个值。

至于计算重复数，它可能有助于直观地考虑其主要因素的数字。将一个数字提高到整数幂意味着将其本身乘以；因此，作为一个素数列表表示，这相当于简单地连接这些列表。例如，6是{2，3}，所以6^3将是{2，2，2，3，3，3}。请注意，如果计算每个素数在列表中出现的次数，x^n将始终与x具有相同的比例，例如6^n的数量将相等于2和3。因此，素数之间的比例相同的范围内的任何两个数字都必须是某个数的幂。

因此，在完整列表中，每个不同比例的素数都重复出现为x^2、x^3、x^4…、(x^3)^2、(x^3)^4.、(x^4)^2……等等，其中x是该比例的最小数；更准确地说，(x^m)^n，其中(x^m) <= 100和2 <= n <= 100。由于(x^m)^n等于x^(m_n)，计数重复项等于计算x^(m_n)也可以是<= 100的方式。