Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vilcheuski's blog

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

9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Как решать O. Cool numbers, не заходит по времени:(
  • 9 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 :)
  • 9 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) , и оставшиеся числа проверяем вручную.
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

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

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