项目EULER#29 [英] PROJECT EULER #29

问题描述

好吧，在通过朴素的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

该程序给出了正确的答案在此处进行检查，但我无法获得已实现的逻辑准确地说，我没有得到如何确定重复项.有人可以帮忙吗?

解决方案

我可能遗漏了一些东西，但是在我看来，该程序给出了错误的答案.一口气.如果将MAX设置为10，则该值将减少2.

我已经读到一些玩家喜欢产生大概的答案，然后对Project Euler服务器进行字典攻击以强行解决问题.其他玩家则认为这与事物的精神背道而驰.

无论如何-这样的算法(从N * M开始并消除重复项)是解决此问题的正确方法，但是就编写此代码而言，这对我来说意义不大.请注意，在任何情况下，int(MAX*(log(i)/log(j)))对舍入误差都非常敏感.但是，即使您使用整数算术消除了该错误源，该程序仍然会给出错误的答案.

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

首先，您必须了解两个数字只有在具有相同的素因式分解的情况下才是相同的.所以只有重复的 a ₁ ^{b ₁} = a _{1时> a 2 ^{b 2}} 和 a ₂ 是相同整数的不同整数幂，我将其称为 x .例如，

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

因此，我们确定对于所有重复项， a ₁ = x ^{e ₁} 和 a ₂ = x ^{e ₂} 表示某些整数 x ， e ₁ 和 e ₁ .

然后讲一点代数，

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 &leb< em> x ^e  &leb< 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).

Well, after solving this problem by naive STL set,I was reading the forum entries,there I find this entry :

 #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;
  }

The author's explanation : 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

This program is giving correct answer check here but I am unable to get the implemented logic,to be precise I am not getting how the duplicates are determined. Could somebody help ?

解决方案

I may be missing something, but it seems to me this program gives the wrong answer. It's off by one. If I set MAX to 10, it's off by two.

I have read that some players like to produce approximate answers and then dictionary-attack the Project Euler servers to brute-force the problem. Other players consider that rather against the spirit of the thing.

Anyway—an algorithm like this (starting with N*M and eliminating duplicates) is the right way to tackle the problem, but as written this code doesn't make much sense to me. Note that in any case int(MAX*(log(i)/log(j))) is very sensitive to rounding error; but even if you eliminate that source of error by using integer arithmetic, the program still gives the wrong answer.

EDIT: How can we (correctly) count the duplicates?

First you must understand that two numbers are only the same if they have the same prime factorization. So there are only going to be duplicates a₁^b₁ = a₂^b₂ when a₁ and a₂ are distinct integer powers of the same integer, which I'll call x. For example,

• 9⁷ = 3¹⁴; this is possible because 9 and 3 are both powers of 3.
• 8⁶ = 4⁹; this is possible because 8 and 4 are both powers of 2.

So we have established that for all duplicates, a₁ = x^e₁ and a₂ = x^e₂ for some integers x, e₁, and e₁.

Then with a little algebra,

a₁^b₁ = a₂^b₂

x^e₁b₁ = x^e₂b₂

e₁b₁ = e₂b₂

Going back to the earlier examples,

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

So to find all duplicates for any given x, you only need to find duplicates for the simpler expression eb where 2 ≤ x^e ≤ 100 and 2 ≤ b ≤ 100.

Here is a picture of that simpler problem, for x=3 and b ranging only from 2 to 10. I've marked two places where there are duplicates.

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

And here are the duplicates:

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   *   *   *   *

The C++ program you found is trying to count them by visiting each pair of overlapping rows i and j, and calculating how much of row i overlaps row j. But again, unless I'm missing something, the program seems hopelessly imprecise. And it misses some pairs of rows entirely (you never have i=9 and j=27, or i=27 and j=81).

这篇关于项目EULER#29的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！