Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 29
1

Сумма по модулю

30.07.2018, 12:32. Просмотров 714. Ответов 2

Найти сумму чисел от 1 до n, делящихся на c1 или c2, по модулю 10^9+7.
1 <= n, c1, c2 <=10^18
(1сек, 128 MiB)

Каким методом решать? (влоб не проходит по времени)
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2018, 12:32
Ответы с готовыми решениями:

Алгоритм определения наибольшего и наименьшего по модулю из чисел (без применения операции взятия по модулю)
Добрый день! Прошу помощи у знатоков. Даны три действительных числа. Записать алгоритм определения...

Дана матрица C[N,N]. Указать, что больше-сумма строки K или сумма эл-ов главной диагонали. Разложить в порядке убывания по модулю
Дана матрица С. Указать, что больше-сумма строки K или сумма эл-ов главной диагонали. Разложить в...

Сумма по модулю 2
Текст программы: text segment 'code' assume CS:text,DS:data begin: mov AX, data mov DS, AX...

Сумма по модулю 2
что будет если 1(+)1 и x(+)0? нельзя ли как -нибудь преобразовать это x1(+)(x2x3)= и...

X – сумма всех чисел из b, c, d, e по модулю больших |a|
Даны целые a, b, c, d, e. Определить максимальное из чисел x/a, x/b, x/c, x/d, x/e, где x – сумма...

2
Mysterious Light
Эксперт по математике/физике
4090 / 2001 / 408
Регистрация: 19.07.2009
Сообщений: 3,018
Записей в блоге: 21
30.07.2018, 14:32 2
Лучший ответ Сообщение было отмечено Chvick как решение

Решение

Сумма всех чисел, делящихся на c1 или с2, есть сумма (1) чисел, делящихся на с1, (2) чисел, делящихся на с2, минус (3) числа, делящиеся на с1 и с2 одновременно.

Сумма чисел от 1 до n есть n(n+1)/2.
Сумма чисел, кратных с1, равно c1*a(a+1)/2, a=floor(n/c1)
Сумма чисел, деляющихся на с1 и с2, равно НОК(с1,с2)*b(b+1)/2 = с1*с2*b(b+1)/(2НОД(c1,c2)), b=floor(n/НОК(с1,с2))

Собственно, считаем
Код
c1*floor(n/c1)(floor(n/c1)+1)/2 + c2*floor(n/c2)(floor(n/c2)+1)/2 - НОК(с1,с2)*floor(n/НОК(с1,с2))(floor(n/НОК(с1,с2))+1)/2
Даже если использовать длинную арифметику и забить на требование взятия модуля, количество действий органичено сверху сравнительно малым числом операций. Очевидно, можно и проще.
2
Sindbad_M
125 / 124 / 37
Регистрация: 23.05.2016
Сообщений: 497
30.07.2018, 14:37 3
---
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2018, 14:37

Сумма положительных и отрицательных по модулю элементов массива
Ребят! а можете помочь вот с такой задачкой. вот условие: Дан массив С. получить и...

Максимальный по модулю элемент массива и сумма элементов
привет. прошу помочь с заданиями в одномерном массиве, состоящем из n вещественных элементов,...

Минимальный по модулю и сумма модулей элементов массива
В одномерном массиве состоящим из n элементов вычислить 1 минимальный по модулю элемент массива 2...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru