Конечное число положений

Количество кратных mm в отрезке [A, B][A,\,B] равно ⌊Bm⌋−⌊A−1m⌋\left\lfloor \frac{B}{m}\right\rfloor -\left\lfloor \frac{A-1}{m}\right\rfloor. При сдвиге tt на mНОД(d, m)\frac{m}{\text{НОД}(d,\,m)} обе границы сдвигаются на кратное mm, поэтому число кратных не меняется. Достаточно t=1, …, mНОД(d, m)t=1,\,\ldots,\,\frac{m}{\text{НОД}(d,\,m)}; эти положительные положения охватывают все возможные остатки.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 2. Количество кратных mm в отрезке [A, B][A,\,B] равно ⌊Bm⌋−⌊A−1m⌋\left\lfloor \frac{B}{m}\right\rfloor -\left\lfloor \frac{A-1}{m}\right\rfloor. При сдвиге tt на mНОД(d, m)\frac{m}{\text{НОД}(d,\,m)} обе границы сдвигаются на кратное mm, поэтому число кратных не меняется. Достаточно t=1, …, mНОД(d, m)t=1,\,\ldots,\,\frac{m}{\text{НОД}(d,\,m)}; эти положительные положения охватывают все возможные остатки.
M=21M=21

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу