Задача 1940 из тимуса, нашел решение в интернете тк сам не смог и наткнулся на ваш разбор тут и он оказался очень похожим на ваш, непонятно несколько моментов: чем являются число ans (которое складывается из +-V) для 100 и почему мы вообще можем такой алгоритм использовать. И каким образом мы выбираем прибавлять число V или нет?Если мы идем по дереву то все время отнимаем, но потом по этим же знаениям поднимаемся и получается что это вычитание не имеет смысла.

задан 25 Май '14 17:59

изменен 25 Май '14 18:20

10|600 символов нужно символов осталось
1

Основой применяемого алгоритма является формула включений и исключений из комбинаторики. Когда берутся все натуральные числа от 1 до 100, то мы хотим узнать, какое их количество не делится ни на одно из простых чисел списка 2, 3, 5, 7 (это частный пример, но на нём всё можно понять). Достаточно легко подсчитать, сколько чисел от 1 до 100 делится на 2. Ясно, что их будет 50. Делящихся на 3 чисел будет 33: это целая часть отношения 100/3. Вообще, для любого натурального $%m$%, будь то 2, 3, 6, 15 или какое угодно число, на $%m$% будут делиться ровно $%[n/m]$% чисел.

Обозначим через $%A_m$% множество тех чисел от 1 до 100, которые кратны $%m$%. Нас здесь интересует число элементов объединения $%|A_2\cup A_3\cup A_5\cup A_7|$%. Согласно формуле включений и исключений, это будет следующая величина: $%|A_2|+|A_3|+|A_5|+|A_7|-|A_2A_3|-|A_2A_5|-|A_2A_7|-|A_3A_5|-|A_3A_7|-|A_5A_7|$%+$%|A_2A_3A_5|+|A_2A_3A_7|+|A_2A_5A_7|+|A_3A_5A_7|-|A_2A_3A_5A_7|$%. Это число элементов в каждом из множеств, минус число элементов в каждом из попарных пересечений, плюс число элементов в каждом из тройных пересечений, минус число элементов в пересечении четырёх множеств, и так далее. Заметим, что $%|A_2A_3|=|A_6|=[\frac{100}6]$%, и аналогично для остальных случаев. И если теперь мы хотим подсчитать, сколько чисел от 1 до $%n=100$% не будут делиться ни на 2, ни на 3, ни на 5, ни на 7, то из общего количества надо будет вычесть то, что получилось выше. Итогом будет $%n-[\frac{n}2]-[\frac{n}3]-[\frac{n}5]-[\frac{n}7]+[\frac{n}{2\cdot3}]+[\frac{n}{2\cdot5}]+[\frac{n}{2\cdot7}]+[\frac{n}{3\cdot5}]+[\frac{n}{3\cdot7}]+[\frac{n}{5\cdot7}]-$% $%[\frac{n}{2\cdot3\cdot5}]-[\frac{n}{2\cdot3\cdot7}]-[\frac{n}{2\cdot5\cdot7}]-[\frac{n}{3\cdot5\cdot7}]+[\frac{n}{2\cdot3\cdot5\cdot7}]$%. Это и есть те прибавления/вычитания, которые используются в ходе алгоритма. Знак "плюс" или "минус" определяется тем, сколько сомножителей у выражения имеется в знаменателе (чётное или нечётное количество, соответственно).

ссылка

отвечен 25 Май '14 18:43

Клааасс,спасибо огромное.Еще раз извиняюсь, а не могли бы вы помочь мне оформить этот алгоритм в виде блок схемы? Был бы безумно признателен

(25 Май '14 19:18) klever

@klever: я очень не люблю делать техническую работу какого бы то ни было рода. Рисунки, таблицы, схемы -- это отнимает кучу времени и не даёт ничего "для души". Объяснить что-то словами -- совсем другое дело.

(25 Май '14 19:29) falcao

@falcao я вас понимаю. Спасибо большое, помогли просто нереально

(25 Май '14 19:34) klever

@falcao а тут не подскажите почему в 7 строке прибавляем 1? Как я понял это описание как-раз вашего метода

         dfs(1,-1,1);

         public static void dfs(int x, int p, int val)
    {
        ans += n / x * val;// +-число V
        if (x < 300 && v[x] != 0) 
            ans++;                
        for (int i = p + 1; i < bt; i++) 
        {
          if (x > n/bas[i])                               
                return;
            dfs(x * bas[i], i, val * -1);
        }
    }
(25 Май '14 20:18) klever

Ой, для меня такие языки программирования -- это "китайская грамота"! :)

(25 Май '14 20:27) falcao

@falcao ахах, это печально. Ну может вы сможете помочь если я постараюсь "перевести". Там идет проверка на то является ли число на которое делим-простым, если да то прибавляем единицу к ответу.Не понимаю почему так.Надеюсь вы понимаете :)

(25 Май '14 20:46) klever

@klever: такое может быть, если подсчитывается количество объектов (например, чисел), обладающего заданным свойством. Оно может быть каким угодно. Перебирая числа из отрезка, проверяем наличие этого свойства для очередного числа, и если оно выполняется, то добавляем 1 к "счётчику" количества таких чисел.

(25 Май '14 21:09) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×147
×20

задан
25 Май '14 17:59

показан
1047 раз

обновлен
25 Май '14 21:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru