Сегодня (10.12.11) в 12:00 MSK состоится вторая индивидуальная олимпиада на neerc. Всем удачи!
Сегодня (10.12.11) в 12:00 MSK состоится вторая индивидуальная олимпиада на neerc. Всем удачи!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 4 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Только меня не система не пускает?
УПД: теперь всё ок.
Кто как делал Д?
У меня упадет по времени когда много разных множителей в факторизации.
ПС. Я делал ДП по маскам + метод включения/выключения. Вышло О(3^p*K^2), где p - кол-во различных простых множителей в числе N.
Я тоже делал дп по маскам, но за divs*k^2*2^p, где divs - число делителей n. p - то же, что и у вас. dp[divisor][mask][count]. divisor - номер текущего делителя. mask - маска покрытых классов эквивалентности простых множителей. Покрытым класс называется тогда, когда мы включили в набор число, в разложение которого данное простое число входит в той же степени, что и в n. count - количество чисел в наборе. Считается число способов добиться состояния mask-count использовав первые divisor делителей. Тогда ответом будет dp[divs][2^p-1][k]. Переходы простые - мы можем добавить текущий множитель несколько раз.
http://ideone.com/2oJMO
Неожиданно, но зашло решение за О(n*sqrt(n)). Просто идем от 1 до n, смотрим на делители числа, если хоть один делитель есть в нашем наборе, прибавляем к ответу, идем дальше.
http://neerc.ifmo.ru/trains/ - раздел "Софт".
я решал Д так:
ну во-первых заметим, что в наборах будут участвовать только делители N (это нетрудно доказать)
далее: посчитаем не то что просится в задаче, а сколько наборов из k элементов у которых НОК != N и отнимем от общего числа наборов - это и будет ответом.
общее число наборов С(k, количество делителей + k - 1) (сочетание с повторениями)
как посчитать количество наборов у которых НОК != N? ну очевидно, что НОК какого-то набора равен N, тогда и только тогда, когда для каждого простого множителя N найдется число в наборе, в котором степень этого простого числа такая же, как в N. теперь понятно, что набор имеет НОК != N, когда не будет выполняться это условие для какого-то простого числа...
то есть посмотрим какие делители числа надо убрать из набора, чтобы в нем не осталось ни одного делителя, делящегося на степень этого числа так для каждого простого множиетля, ну очевидно, что будут делители делящиеся на степень каких то 2х простых множителей, 3х, 4х... и т.д. то есть нужна будет формула включения-исключения... ну еще конечно понадобиться деление по модулю, для вычисление С-шек.... как то так
вот код