Задать вопрос
@timkin1
cpp

Как быстро найти остаток от суммы цифр?

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

Программе подается число (возможно очень большое), нужно просуммировать все числа до этого числа и найти остаток от деления от числа, которое также подается программе. Если первым параметром дать большое число, то программа выполняется очень долго. Необходимо оптимизировать данный процесс. Как это можно сделать?
Заранее спасибо!
  • Вопрос задан
  • 242 просмотра
7 комментариев
Подписаться 1 Простой 7 комментариев
Пригласить эксперта
Ответы на вопрос 2
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
Если первым параметром дать большое число, то программа выполняется очень долго.

А если вместо суммирования чисел воспользоваться формулой суммы арифметической прогрессии n * (n + 1) / 2 ?
Насколько велико "большое число"?
Ответ написан
1 комментарий
1 комментарий
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
(1+2+...+n)%k = (n*(n+1)/2)%k
= ((n/2)%k * (n+1)%k)%k, для чётных n
= (n%k * ((n+1)/2)%k)%k, для нечётных n
Ответ написан
Комментировать
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
DevOps-инженер
САМО-Софт • Москва
До 150 000 ₽
Программист 1С
Виктория • Москва
от 300 000 ₽
C# разработчик
САТЕЛ
от 120 000 до 200 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Софт на js
19 апр. 2024, в 13:31
10000 руб./за проект
Разработка Pwa сайта
19 апр. 2024, в 13:12
35000 руб./за проект
Доработать вебпроект со стеком: yii2, jquery, vue
19 апр. 2024, в 13:06
6000 руб./за проект
Ещё заказы