KostyaVilcheuski's blog

By KostyaVilcheuski, 6 years ago, In Russian,
Подскажите, пожалуйста, как решалась задача D(про игру Пуха и Слонопотама). Спасибо.
 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

6 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Как решать O. Cool numbers, не заходит по времени:(
  • 6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i used precalc, there are only 33 cool numbers between 1 and 100000000 :)
  • 6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ну можно вообще на локалке прекалк сделать для отрезков длины 100000, к примеру, получится массив из 1000 ответов, и далее стандарт - F(l, r) = f(r) - f(l - 1), ну и далее посчитаем  f(x). ( нацело), плюсуем к ответу precalc(k), и оставшиеся числа проверяем вручную.
  • 6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    перебрать пары чисел от 2 до 32. и проверять их на взаимную простоту.

    если они взаимно просты, то lcm=i*j;

    и начинаем возводить последовательно числа от 2,3,4,... в степень lcm.

    если при возведении числа в степень получилось число большее правой границы, то брейкаемся, иначе смотрим есть ли уже это число в сете, если есть,  то ничего не делаем, а если нет, то добавляем в сет число и плюсуем к ответу 1.

  • 6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Можно перебрать показатели степеней. Очевидно, что они не больше 26-27. Итак, теперь у нас есть два показателя, которые взаимно просты. Таких пар уже совсем мало. Для каждой пары переберем одно из оснований степени, посмотрим, входит ли полученное число в промежуток, если входит, то бинарным поиском подберем второе основание. Если оно существует, то добавим число в ответ. Это работает очень быстро.