Сумма остатков

[Cancre]

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

[Cancre]

Упрощающие обозначения:

$\alpha = \left\lfloor\frac{k}{a}\right\rfloor$

$r= n \bmod k$

$\nu=\left\lfloor\frac{r-1}{\alpha}\right\rfloor$

$q=(r-1) \bmod \alpha$

$ x \operatorname {red} y = \begin{cases} x \bmod y,&\text{если y не делит x;}\\ y,&\text{если y делит x;}\\ 0,&\text{если x=0;} \end{cases}$

$$\sum\limits_{j=1}^{n}(aj \bmod k)=\frac{ak(k+1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+ a( \sum\limits_{j=1}^{\nu}\frac{\alpha(\alpha+1)}{2}+\sum\limits_{j=1}^{r \bmod \alpha}(j \,red\,\alpha))+(a\alpha-k)\sum\limits_{j=0}^{r-1}\left\lfloor\frac{j}{\alpha}\right\rfloor=$$

$$=\frac{ak(k+1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+a(\nu\cdot\frac{\alpha(\alpha+1)}{2}+\frac{(r\,red\,\alpha)((r\,red\,\alpha)+1)}{2})+(a\alpha-k)(\frac{\alpha\nu(\nu+1)}{2}-\nu(\alpha-q-1))$$

Данная формула верна при взаимно простых a и k, а также при условии $\left\lfloor\frac{k-a}{a}\right\rfloor > 0$
Если $\left\lfloor\frac{k-a}{a}\right\rfloor = 0$ , тогда остатки в ряде по вычетам зеркально меняются местами и пока не ясно, как это отражение выразить в формуле.

[Cancre]

В случае $\left\lfloor\frac{k-a}{a}\right\rfloor=0$ из полной суммы вычетов $\frac{ak(k+1)}{2}$ нужно вычесть $\sum\limits_{j=0}^{k-r}((k-a)j \bmod k)$

Ещё нужно ввести функцию, учитывающую нули при соответствующих остатках и случай $a=k$

$$\chi_m (x,y) =\begin{cases} 0,&\text{если $x \bmod y = 0$;}\\ 1,&\text{если $x \bmod y > 0$} \end{cases}$$

И добавляется НОД(a,k).
Всё вместе:

$$\sum\limits_{i=1}^{n}(ai \bmod k)= \chi_m (a,k)\frac{ak(k+1)}{2\gcd(a,k)}\left\lfloor\frac{n}{k}\right\rfloor$+\begin{cases} \chi_m (aj,k)$$\sum\limits_{j=1}^{r}(aj \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor>0$;}\\ \frac{ak(k+1)}{2\gcd(a,k)}-\chi_m ((k-a)j,k)$$\sum\limits_{j=1}^{k-r}((k-a)j \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor=0$} \end{cases}$$

[Sonic86]

Я пока в основном по обозначениям:

Cancre в сообщении #1094492 писал(а):

$\left\lfloor\frac{k-a}{a}\right\rfloor=0$

Изврат: $\Leftrightarrow k \in [a;2a) $.

Cancre в сообщении #1094492 писал(а):

$\left\lfloor\frac{k-a}{a}\right\rfloor>0$

Аналогично: $k\geqslant 2a$.

Cancre в сообщении #1094492 писал(а):

$$\chi_m (x,y) =\begin{cases} 0,&\text{если $x \bmod y = 0$;}\\ 1,&\text{если $x \bmod y > 0$} \end{cases}$$

индекс $m$ зачем? можно стереть.
и вообще самое короткое, что здесь можно писать, это - нотация Айверсона: $\chi (x,y)=[x\nmid y]$ (здесь $[P]=1 \Leftrightarrow P\text{ истинно}$, иначе $[P]=0$)

Cancre в сообщении #1094492 писал(а):

$\chi_m (aj,k) \sum\limits_{j=1}^{r}(aj \bmod k)$

переменная суммирования вне суммы, кроме того, $\chi_m (aj,k)$ сильно упрощаемо.

Cancre в сообщении #1094492 писал(а):

$\chi_m ((k-a)j,k)$

Аналогично + еще более упрощаемо.

И, теряя уже надежду что-то донести, в 3-й раз Вам говорю: достаточно рассмотреть случай $\gcd(a,k)=1$, общий случай тривиально к нему сводится.

Но пока, все что я вижу, похоже на попытку итерирования формулы для НОДа, что, как я уже писал, бесполезно.

[Cancre]

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

Я пока в основном по обозначениям:

Cancre в сообщении #1094492 писал(а):

$\left\lfloor\frac{k-a}{a}\right\rfloor=0$

Изврат: $\Leftrightarrow k \in [a;2a) $.

Но именно так оно и есть. )))

-- 26.01.2016, 22:25 --

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

Cancre в сообщении #1094492 писал(а):

$$\chi_m (x,y) =\begin{cases} 0,&\text{если $x \bmod y = 0$;}\\ 1,&\text{если $x \bmod y > 0$} \end{cases}$$

индекс $m$ зачем? можно стереть.

Вместо m хотел mod , но система не дала.

-- 26.01.2016, 22:31 --

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

Cancre в сообщении #1094492 писал(а):

$\chi_m (aj,k) \sum\limits_{j=1}^{r}(aj \bmod k)$

переменная суммирования вне суммы,

Конечно же под знаком суммы

$$\sum\limits_{i=1}^{n}(ai \bmod k)= \chi_m (a,k)\frac{ak(k+1)}{2\gcd(a,k)}\left\lfloor\frac{n}{k}\right\rfloor$+\begin{cases} $$\sum\limits_{j=1}^{r}\chi_m (aj,k)(aj \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor>0$;}\\ \frac{ak(k+1)}{2\gcd(a,k)}-$$\sum\limits_{j=1}^{k-r}\chi_m ((k-a)j,k)((k-a)j \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor=0$} \end{cases}$$

-- 26.01.2016, 22:40 --

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

И, теряя уже надежду что-то донести, в 3-й раз Вам говорю: достаточно рассмотреть случай $\gcd(a,k)=1$, общий случай тривиально к нему сводится.

Но пока, все что я вижу, похоже на попытку итерирования формулы для НОДа, что, как я уже писал, бесполезно.

95% времени искал формулы именно для (а,к)=1
И, вообще-то, то что искал нашёл. В две формулы, но хоть так, я очень доволен. Так что, дааалеко не бесполезно.

Спасибо за замечания. Может, в каких-то моментах Вам казалось, что что-то не доносили, но это не так. Все замечания обдумывались.

[whitefox]

($\chi_{mod}$)

Cancre в сообщении #1094516 писал(а):

Вместо m хотел mod , но система не дала.

используйте фигурные скобки для группировки.

$\chi_{mod}$

$\chi_{mod}$