Преобразование одной суммы [Теория чисел]

[arseniiv]

У меня с такими суммами не ахти. Кстати, не смотрели в «Конкретной математике»? Хотя такое чувство, что эта сумма как раз оттуда.

[Whitaker]

arseniiv
нет не смотрел, но обязательно посмотрю.
Спасибо за ссылку
Эта задачка из книжки "Арифметика. Алгоритмы. Сложность вычислений" Чубарикова-Гашкова.

[Sonic86]

Блин, попытался найти сумму сам.
Прежде всего: берем $x=1,n=2,m=2\Rightarrow d=1$. Слева получаем $0+1+1+2=4$, а справа $\frac{(2-1)(3-1)}{2}+0+1=2\neq 4$. Проверьте.
У меня получилось так:

$$S=\sum\limits_{k=0}^n\frac{x+mk}{n}-\frac{(x+mk)\mod n}{n}=\frac{n+1}{n}x+\frac{m(n+1)}{2}-\frac{1}{n}\sum\limits_{k=1}^n\frac{(x+(m\mod n)k)\mod n}{n}=$$

$$=x+n\left[\frac{x}{n}\right]+\frac{m(n+1)}{2}-([x]+\frac{n+1}{2}[m\mod n > 0])$$

(последнюю сумму брал из соображений, что все слагаемые пробегают полную систему вычетов, либо все равны $[x]$).
Фигня какая-то короче
Надо хоть на компе проверить...

[Whitaker]

Sonic86 в сообщении #562909 писал(а):

Прежде всего: берем $x=1,n=2,m=2\Rightarrow d=1$

$d=$НОД$(m,n)$. Так как $m=n=2$, то $d=2$, а у Вас $d=1$.

[Sonic86]

Whitaker в сообщении #562954 писал(а):

$d=$НОД$(m,n)$. Так как $m=n=2$, то $d=2$, а у Вас $d=1$.

Вру: $m=2, n=3, x=1$. Проверьте.

[Whitaker]

Sonic86
Вы правы. Оказывается условие задачи такое:
$\sum \limits_{k=0}^{n-1}\Big[\dfrac{x+mk}{n}\Big]=d\Big[\dfrac{x}{d}\Big]+\dfrac{(m-1)(n-1)}{2}+\dfrac{d-1}{2}$
т.е. суммирование идет от $0$ до $n-1$, а не от $0$ до $n$.

$\sum \limits_{k=0}^{n-1}\Big[\dfrac{x+mk}{n}\Big]=\sum \limits_{k=0}^{n-1}\Big[\dfrac{[x]+mk}{n}\Big]$$=\sum \limits_{k=0}^{n-1}\dfrac{[x]+mk}{n}-\sum \limits_{k=0}^{n-1}\Big\{\dfrac{[x]+mk}{n}\Big\}=[x]+\dfrac{m(n-1)}{2}-\sum \limits_{k=0}^{n-1}\Big\{\dfrac{[x]+mk}{n}\Big\}$
Если $(m,n)=1$, то числа $[x], [x]+m, [x]+2m, \dots, [x]+(n-1)m$ дают различные остатки при делении на $n$.
Получаем, что:
$\sum \limits_{k=0}^{n-1}\Big\{\dfrac{[x]+mk}{n}\Big\}=\sum \limits_{k=0}^{n-1}\Big\{\dfrac{k}{n}\Big\}=\sum \limits_{k=0}^{n-1}\dfrac{k}{n}=\dfrac{n-1}{2}$
Отсюда:
$\sum \limits_{k=0}^{n-1}\Big[\dfrac{x+mk}{n}\Big]=[x]+\dfrac{(m-1)(n-1)}{2}$, когда $(m,n)=1$
Случай $(m,n)=d>1$ иисследуется аналогично.
Как отметил arseniiv делится на $d$ и сводится к первому случаю и получается нужный ответ.

[Sonic86]

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

[Whitaker]

Sonic86
да понял.
Спасибо большое Вам за помощь в решении задачи!

[Whitaker]

Sonic86
да понял.
Спасибо большое Вам за помощь в решении задачи!

[arseniiv]

Хорошо всё разрешилось.

[Whitaker]

arseniiv
да согласен. Ваша подсказка очень помогла
Вам также большое спасибо!

[arseniiv]

Это просто удачно совпала моя догадка с вашим решением.