ПРОЕКТ 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))) очень чувствителен к ошибке округления; но даже если вы устраните этот источник ошибок с помощью целочисленной арифметики, программа все равно даст неправильный ответ.

РЕДАКТИРОВАТЬ: Как мы можем (правильно) подсчитать дубликаты?

Сначала вы должны понять, что два числа одинаковы, если они имеют одинаковую простую факторизацию. Так что будут только дубликаты a ₁ ^{b ₁} = a ₂ ^{b ₂} при a ₁ и a ₂ - это различные целочисленные степени одного и того же целого числа, которое я назову x . Например,

• 9 ⁷ = 3 ¹⁴ ; это возможно, потому что 9 и 3 являются степенями 3.
• 8 ⁶ = 4 ⁹ ; это возможно, потому что 8 и 4 являются степенями 2.

Итак, мы установили, что для всех дубликатов a ₁ = x ^{e ₁} и a ₂ = x ^{e ₂} для некоторых целых чисел x , e ₁ и e ₁ .

Затем с небольшой алгеброй,

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

x ^{e ₁ b ₁} = x * ** одна тысяча сто тридцать четыре тысяча сто тридцать-пять * е * 1 136 * ₂ B * 1 141 * 2

e ₁ b ₁ = e ₂ b ₂

Возвращаясь к более ранним примерам,

• 9 ⁷ = 3 ¹⁴ , потому что 2 & times; 7 = 1 & times; 14.
• 8 ⁶ = 4 ⁹ , потому что 3 & times; 6 = 2 & times; 9.

Таким образом, чтобы найти все дубликаты для любого данного x , вам нужно только найти дубликаты для более простого выражения eb , где 2 & le; x ^e & le; 100 и 2 & le; b & le; 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).

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 <em>n), считая количество дубликатов подсчитывает, каким образом x ^ (m n) также может быть <= 100. </p>

Answer 3

сначала он устанавливает res на 99 * 99 в строке 6, потому что MAX был определен как 100. Затем он входит в цикл с условием, что i меньше MAX. затем он входит в этот цикл псевдокода

int i;
int j;
int x=2;

для (j = i ² ; j <= MAX, j = i <sup>x )
{
res = res- (MAX * ( ^j log (i)) +1;
х ++;
}

извините, но вы не используете <pre><code> выше; но если бы я сделал, я не мог бы использовать <sup>

Обратите внимание, log(a)/log(x) совпадает с ^x log (a)

---

комментирует вопрос, потому что <sup> там не работает:

² log (2) = 1, потому что 2 ¹ = 2
² log (4) = 2, потому что 2 ² = 2
log (x) == ¹⁰ log (x)
log (10) = 1

^г log (x) = y => g ^y = x

Answer 4

Есть (по крайней мере) два способа решения этой проблемы. Один из них состоит в том, чтобы начать отсчет различных значений с 0 и добавить один для каждого вычисленного значения, которое раньше не было видно. Другой способ - рассчитать максимальное количество значений, а затем вычесть одно для каждого дубликата.

Постер пытается второй мет. a может варьироваться от 2 до 100 для 99 значений, как и b, так что есть 99 * 99 полученных значений. Затем автор пытается вычесть повторяющиеся значения, чтобы получить правильный ответ.

Редактировать: Тем не менее, автор написал неверный алгоритм. Например, установка MAX = 8 или 9. Для 8 это должно дать 44, но это даст 45. Для 9 это должно дать 54, но даст 56. Либо им повезло, и они столкнулись с алгоритмом, который дает правильный ответ для некоторых входных данных, либо они разработали алгоритм, который работал, когда MAX = 100, но не для всех других значений.