Количество отрезков в квадратной решетке

[MrDindows]

malphunction в сообщении #728475 писал(а):

MrDindows в сообщении #728244 писал(а):

Можно источник задачи?
Я знаю решение за $O(n\ln{n})$ и вроде как за $O(n)$

Это задача 415 из Project Euler. А что у Вас за решение?

Ключевая идея - считать от обратного, то-есть от общего числа отрезков в квадрате отнять количество тех, которые содержат в себе ровно 2 целочисленные точки. Я, кстати, очень удивился, что никто её не предложил, а полезли все в страшные дебри=)

И так, с общим числом отрезков понятно: $\frac{(n+1)^2((n+1)^2-1)}{2}$ .
Нужно найти количество отрезков с двумя точками.
Заметим, что каждый такой отрезок задаётся вектором $(p;q)$, где $p$ и $q$ - взаимно простые числа, одно из них, например, $q$ может быть отрицательным. Также, очевидно, что для каждого такого вектора существует
$(n+1-p)(n+1-q)$ отрезков в квадрате, содержащих ровно 2 точки.
И вот мы уже получили решение за $О(n^2\cdot\ln(n))$ или за $О(n^2)$ - перебрать все пары взаимно простых, ну и посчитать искомое количество.
Теперь нужно ускорить этот подсчёт, чтоб не перебирать все пары.
Возьмём число $p$, по известному свойству, количество чисел, взаимно простых с $p$ и меньших его равно $\varphi(p)$. А их сумма равна: $\frac{p\cdot\varphi(p)}{2}$. Таким образом, нам осталось просуммировать
$\sum\left(\left(n+1-p\right)\cdot\left(\varphi(p)\cdot(n+1)-\frac{p\cdot\varphi(p)}{2}\right)\right)$. (и не забыть учесть единичные отрезки, и пары с отрицательны $q$).
А это можно сделать за $O(n\sqrt{n})$, если перебирать $p$ и считать $\varphi(p)$ в лоб, либо если запустить рекурсию, и получать все натуральные числа из простых, что тем самым даст возможность поддерживать значение $\varphi$ и изменять на каждом шаге за $O(1)$. Итого $O(n)$. Но, увы, тут возникает сложность для $n>10^9$, ибо мы не сможем получить достаточно большие простые числа.
Конечно, алгоритм ещё можно попробовать улучшить, или даже свернуть формулу.
п.с.
Вот, как пример, $O(n\sqrt{n})$: http://ideone.com/OzPUrR
п.с2
Прочитал я ту задачу, как-то там ещё сложнее, чем то, что вы написали=)

[nikvic]

MrDindows в сообщении #728487 писал(а):

ибо мы не сможем получить достаточно большие простые числа

О взаимной простоте я говорил.
Можно обдумать вариант алгоритма, оперирующего с цепными дробями - там она получается автоматом.
Да, самая "длинная" дробь - у последовательности Фибоначчи.

Задача тяготеет к описанию множества правильных дробей при ограничении на знаменатель.

[malphunction]

MrDindows в сообщении #728487 писал(а):

Ключевая идея - считать от обратного, то-есть от общего числа отрезков в квадрате отнять количество тех, которые содержат в себе ровно 2 целочисленные точки.

Блиииин, точно!!!!! Вы гений :)

Сейчас попробую всю задачу решить, потом расскажу, как 415-ая сводится к этой.

[malphunction]

MrDindows в сообщении #728487 писал(а):

И так, с общим числом отрезков понятно: $\frac{(n+1)^2((n+1)^2-1)}{2}$ .

Не, не сходится. У меня-то между двумя точками может быть несколько отрезков, а по этой формуле подразумеватеся один.
Пример: отрезок $(1,1) - (4,4)$, тремя точками он может быть представлен двумя способами: $(1,1) - (2,2) - (4,4)$, $(1,1) - (3,3) - (4,4)$

Так что формула вычисления общего количества многозвенных отрезков другая.

Вроде бы и для такого случая формула проста, но у нас уже ночь, голова не варит, так что завтра посчитаю...

-- Вс май 26, 2013 23:15:36 --

nikvic в сообщении #728490 писал(а):

MrDindows в сообщении #728487 писал(а):

ибо мы не сможем получить достаточно большие простые числа

О взаимной простоте я говорил.
Можно обдумать вариант алгоритма, оперирующего с цепными дробями - там она получается автоматом.
Да, самая "длинная" дробь - у последовательности Фибоначчи.

Задача тяготеет к описанию множества правильных дробей при ограничении на знаменатель.

Пожалуйста, расскажите яснее, что-то не улавливаю суть Вашего предложения.

[nikvic]

malphunction в сообщении #728587 писал(а):

nikvic в сообщении #728490 писал(а):

MrDindows в сообщении #728487 писал(а):

ибо мы не сможем получить достаточно большие простые числа

О взаимной простоте я говорил.
Можно обдумать вариант алгоритма, оперирующего с цепными дробями - там она получается автоматом.
Да, самая "длинная" дробь - у последовательности Фибоначчи.

Задача тяготеет к описанию множества правильных дробей при ограничении на знаменатель.

Пожалуйста, расскажите яснее, что-то не улавливаю суть Вашего предложения.

Пока - мысли вслух. Оттрезки лежат на прямых, наклон которых выражается "короткими" несократимыми дробями. Несократимые дроби генерируются как цепные.

[MrDindows]

malphunction в сообщении #728587 писал(а):

Не, не сходится. У меня-то между двумя точками может быть несколько отрезков, а по этой формуле подразумеватеся один.
Пример: отрезок $(1,1) - (4,4)$, тремя точками он может быть представлен двумя способами: $(1,1) - (2,2) - (4,4)$, $(1,1) - (3,3) - (4,4)$

Тю блин=)
Тогда формулировать надо было как-то иначе : множество точек, лежащих на одной прямой. А то - отрезок-отрезок... Он в геометрии такой один=)

[malphunction]

MrDindows в сообщении #728687 писал(а):

malphunction в сообщении #728587 писал(а):

Не, не сходится. У меня-то между двумя точками может быть несколько отрезков, а по этой формуле подразумеватеся один.
Пример: отрезок $(1,1) - (4,4)$, тремя точками он может быть представлен двумя способами: $(1,1) - (2,2) - (4,4)$, $(1,1) - (3,3) - (4,4)$

Тю блин=)
Тогда формулировать надо было как-то иначе : множество точек, лежащих на одной прямой. А то - отрезок-отрезок... Он в геометрии такой один=)

Так и сформулировано было, отрезок, состоящий хотя бы из трёх точек.
Надо было мне точнее сформулировать: отрезок с концами на точках решетки, содержащий внутри себя хотя бы ещё одну точку решетки. Но, вообще-то, в дальнейшем обсуждении я, в ответе Sonic86, объяснял, какие отрезки мне нужные и приводил примеры.

[Corwin]

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

Как-то так:
$T_2(n) = \sum_{\frac{n}{2} < x \leqslant n} \sum_{1 \leqslant y < x}4 (n+1-x)(n+1-y) \cdot \theta(x,y) \ $,
где
$\theta(x,y) = \left\{\begin{matrix} 1, (x, y) = 1\\ 0, (x, y) \ne 1 \end{matrix}\right.$

$\theta(x,y) = \sum_{d|(x,y)}\mu(d)$

теперь сюда нужно подставить $x = i \cdot d$ и $y = j \cdot d$ и поменять порядок суммирования

(Оффтоп)

Почему у меня пределы суммирования не под значком суммы, а сбоку?

[Corwin]

$T_2(n) = \sum_{\frac{n}{2} < x \leqslant n} \sum_{1 \leqslant y < x}\sum_{d|(x,y)} 4 (n+1-x)(n+1-y)\mu(d)$
теперь сюда нужно подставить $x = i \cdot d$ и $y = j \cdot d$ и поменять порядок суммирования

-- 30.05.2013, 12:40 --

Упс!
Не заметил, что есть вторая страница, и что считать через "ровно 2" уже предложили :).

[Corwin]

$$ T_2(n) = 4 \sum_{1 < d \leqslant \frac{n}{2}} \mu(d) \sum_{\frac{n}{2d} < i \leqslant \frac{n}{d}} (n+1-id) \sum_{ 1 \leqslant j < i} (n+1-jd) $$

$$ T_2(n) = 2 \sum_{1 < d \leqslant \frac{n}{2}} \mu(d) \sum_{\frac{n}{2d} < i \leqslant \frac{n}{d}} (n+1-di) (2(n+1) - di) (i-1) $$

$$ T_2(n) = n \sum_{1 < d \leqslant \frac{n}{2}} \mu(d) \frac{2d^2-9d(n+2)+4n^2+21n+24}{12d} $$

Наверняка, я где-нибудь ошибся в преобразованиях - уж слишком они громоздкие :)

[iifat]

(Оффтоп)

Corwin в сообщении #730277 писал(а):

Почему у меня пределы суммирования не под значком суммы, а сбоку?

Потому что формула не выделенная, а в строку. Либо вдвое больше баксов (окаймлять двойными), либо вот так вот:
$T_2(n) = \sum\limits_{\frac{n}{2} < x \leqslant n} \sum\limits_{1 \leqslant y < x}4 (n+1-x)(n+1-y) \cdot \theta(x,y)$

[malphunction]

Corwin писал(а):

Наверняка, я где-нибудь ошибся в преобразованиях - уж слишком они громоздкие :)

Я пока не вник в Ваши формулы, потому что сходу вопрос: как от прямых перейти к отрезкам? Мне нужно не количество прямых считать, а количество отрезков. Это в формуле учитывается?