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 a1b1 = a2b2 when a1 and a2 are distinct integer powers of the same integer, which I'll call x. For example,
- 97 = 314; this is possible because 9 and 3 are both powers of 3.
- 86 = 49; this is possible because 8 and 4 are both powers of 2.
So we have established that for all duplicates, a1 = xe1 and a2 = xe2 for some integers x, e1, and e1.
Then with a little algebra,
a1b1 = a2b2
xe1b1 = xe2b2
e1b1 = e2b2
Going back to the earlier examples,
- 97 = 314 because 2×7 = 1×14.
- 86 = 49 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 ≤ xe ≤ 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).
first, it sets res to 99*99 at line 6, because MAX was defined as 100. Then it enters a loop, with the condition that i is smaller than MAX. then it enters this pseudocode loop
int i;
int j;
int x=2;
for( j = i2; j <= MAX , j = ix)
{
res = res- (MAX* ( jlog(i) )+1;
x++;
}
sorry 'bout the not using <pre><code> above; but if I did I could not use <sup>
Please note log(a)/log(x) is the same as xlog(a)
comments on question because <sup> does not work there:
2log(2) = 1 because 21 = 2
2log(4) = 2 because 22 = 2
log(x) == 10log(x)
log(10) = 1
glog(x) = y => gy = x
Well, the question involves ways to combine two numbers chosen from a range. There are 99 possible numbers, so the number of combinations is 99 * 99, with possible duplicates. His basic algorithm here is to figure out how many duplicates are present, and subtract that value from the maximum.
As for counting duplicates, it might help intuitively to think of the numbers in terms of their prime factors. Raising a number to an integer power means multiplying it by itself; so, represented as a list of primes, this is equivalent to simply concatenating the lists. For instance, 6 is {2, 3}, so 6^3 would be {2, 2, 2, 3, 3, 3}. Note that if you count how many times each prime appears in the list, x^n will always have the same proportions as x, for instance 6^n will have an equal quantity of 2's and 3's. So, any two numbers in the range with the same proportion between primes must both be powers of some number.
So, in the full list, each distinct proportion of prime factors will appear repeatedly as x^2, x^3, x^4..., (x^3)^2, (x^3)^4..., (x^4)^2..., etc., where x is the smallest number with that proportion; more precisely, (x^m)^n where (x^m) <= 100 and 2 <= n <= 100. Since (x^m)^n is equal to x^(mn), counting duplicates amounts to counting the ways that x^(mn) can also be <= 100.
There are (at least) two ways to approach this problem. One is to start your count of distinct values at 0, and add one for each calculated value that hasn't been seen before. The other way is to calculate the maximum number of values, and then subtract one for each duplicate.
The poster is attempting the second methed. a can range from 2 to 100 for 99 values, as can b, so there are 99 * 99 produced values. The poster then attempts to subtract the duplicate values to get the correct answer.
Edit: However, the poster has written an incorrect algorithm.
For instance, setting MAX = 8 or 9. For 8 it should give 44 but it gives 45. For 9 it should give 54 but gives 56. Either they lucked out and happened across an algorithm that gives the correct answer for some inputs, or they reverse-engineered an algorithm that worked when MAX = 100 but not for all other values.
