1 Тема от MSDN Отредактировано MSDN (2010-08-24 10:25:27)

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: SEERC 2008

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

У меня вопросы по нескольким задачам.

Sky code

http://acmicpc-live-archive.uva.es/nuev … php?p=4184

Собственно нашел на топ кодере обсуждение небольшое данной задачи... но все что я из него понял это то что нужно считать четверки чисел у которых НОД больше 1. Это значит что у всех четырех чисел есть как минимум один общий простой делитель...

GCD Determinant

http://acmicpc-live-archive.uva.es/nuev … php?p=4190

Нашел код решение этой задачи. Там просто перемножается все значения функций эйлера для всех чисел множества.... Собственно объяснения почему именно это будет ответом не нашел....

Quick answer

http://acmicpc-live-archive.uva.es/nuev … php?p=4188

Собственно сразу подумал про систему не пересекающихся множеств, но вот как реализовать действие изоляции одной вершины?

2 Ответ от Zayakin_Andrey Отредактировано Zayakin_Andrey (2010-08-24 14:20:32)

  • Зарегистрирован: 2009-06-21
  • Сообщений: 28

Re: SEERC 2008

по Quick Answer удалить значит создать новое множество из одной вершины, идентификатор которой будет M , где M наименьший достпуный  идентификатор, и соответственно предыдущий идентификатор вершины уже использовать нельзя.
http://ideone.com/ZovYa
можешь посмотреть код

3 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: SEERC 2008

Sky code:

посчитаем массив s, s_i - это количество четверок чисел таких, что каждое из них делится на i. Ответом будет сумма по i от 1 до 10000 s_i*mu(i), где mu(i) - функция Мёбиуса

4 Ответ от mincer

  • mincer
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-19
  • Сообщений: 12

Re: SEERC 2008

Интересно, а почему такое решение Sky Code корректно...

5 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: SEERC 2008

По поводу Quick answer
Спасибо не заметил в условии строчку про то что при дисконекте, связи других компов не разрываются - так действительно все просто....

6 Ответ от MSDN Отредактировано MSDN (2010-08-25 08:20:52)

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: SEERC 2008

Sky Code

То есть по сути если присмотреться получаеться формула включений и исключений. То есть генерим решетом все простые числа... затем считаем сколько всего способов набрать 4 числа из всех чисел... затем отнимаем числа которые состоят из одного простого числа (в смысле количество четверок чисел которые делятся на одно и тоже простое число), затем прибавляем которые состоят из двух, потом отнимаем из трех... и т.д. 
А вот такой вопрос вы к этому решению пришли из каких то соображений теории чисел или нет? Просто может теорема какая нибудь есть....

7 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: SEERC 2008

Спасибо сдал Sky Code smile

8 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: SEERC 2008

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