Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
#1

Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B - C++

20.04.2013, 18:22. Просмотров 1596. Ответов 37
Метки нет (Все метки)

Условие
Ватсон поставил Рыбке простую задачу - найти сумму чисел меньших N, которые должны делиться или на A, или на B, и вывести ее остаток от деления на 1000000007 (10^9 + 7). Помогите Рыбке справиться с этой задачей.

Входные данные
В одной строке заданы три целых числа N, A и .
1 <= N, A, B < 10^18.

Выходные данные
Рассчитать остаток от деления необходимой суммы на 1000000007.

Пример
Вход: 7 2 3
Вывод: 15

Пояснение
Числа, которые делятся на 2: 2, 4, 6. Числа, которые делятся на 3: 3, 6.
Сумма этих чисел: 2 + 3 + 4 + 6 = 15

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
 
using namespace std;
 
int main(void)
{
    long long n, a, b, sum = 0;
    cin>>n>>a>>b;
 
    for (long long i = a; i < n; i += a) if (i % b != 0) sum += i;
    for (long long i = b; i < n; i += b) sum += i;
 
    cout<<(sum % 1000000007);
    return 0;
}
На 53 тесте превысило лимит времени 500 мс

Как еще больше оптимизировать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 18:22
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B (C++):

Определить количество чисел, меньших n, которые не делятся на 11 - C++
Не знаю как решить. Определить количество натуральных чисел меньших n. Которые не делятся на 11. Протестировать на n=10, n=100,n =1000.

нужно написать программу, находящую количество чисел меньших x, которые делятся в точности на три простых числа. - C++
Мне нужно написать программу, находящую количество чисел меньших x, которые делятся в точности на три простых числа. Кто-нибудь может...

Найти сумму тех чисел, которые делятся на 5 или на 7 - C++
дано натуральные числа от 1 до 50. найти сумму тех из них, которые делятся на 5 или на 7!!!! зделать циклом с предпосылка

Найти сумму и количество чисел, которые делятся на 5 или 7 - C++
1)Даны натуральные числа от Х до 50. Найти сумму и ко-во тех из них, которые делятся на 5 или 7.

Вывести на экран сумму чисел от 0 до 1000, которые делятся нацело на 3 или 5 - C++
Решила сделать задачку: Вывести на экран сумму чисел от 0 до 1000 , что делятся нацело на 3 или 5 . Но как всегда не правильно сделала,...

Найти среди компонентов файла количество чисел, которые делятся на 2, но не делятся на 4 - C++
Заполнить файл f целыми числами, полученными с помощью генератора случайных чисел. Найти среди компонентов файла количество чисел, которые...

37
salam
173 / 154 / 17
Регистрация: 10.07.2012
Сообщений: 761
20.04.2013, 19:18 #2
числа, делящиеся на (а) - арифметическая прогрессия; числа, делящиеся на (в) - арифметическая прогрессия; числа, делящиеся на (а и в) - арифметическая прогрессия...
разбейте на куски так, чтобы ответ не переполнял тип, и будьте счастливы.
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 19:20  [ТС] #3
Цитата Сообщение от salam Посмотреть сообщение
разбейте на куски так, чтобы ответ не переполнял тип, и будьте счастливы.
Что разбить на куски?
0
salam
173 / 154 / 17
Регистрация: 10.07.2012
Сообщений: 761
20.04.2013, 20:36 #4
высчитаете сумму арифметической прогрессии от 1 до N. если будете считать так, что тип переполнится, ибо N <= 10^18. поэтому поделите прогрессию на несколько частей и для каждой считайте ответ.
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 20:39  [ТС] #5
Цитата Сообщение от salam Посмотреть сообщение
высчитаете сумму арифметической прогрессии от 1 до N. если будете считать так, что тип переполнится, ибо N <= 10^18. поэтому поделите прогрессию на несколько частей и для каждой считайте ответ.
Может я уже не соображаю, но не пойму что вы мне предлагаете.
Мой код в 1 сообщении полностью рабочий, но он не прошел 53-ю проверку системы - превысил лимит времени выполнения в 500 мсек. И я спрашиваю как его еще больше оптимизировать...
0
dr.curse
392 / 348 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 20:42 #6
A1exSun, а можно ссылку на задачу?
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 20:44  [ТС] #7
Цитата Сообщение от aram_gyumri Посмотреть сообщение
A1exSun, а можно ссылку на задачу?
Не получится, система закрыта. Только для своих
Это с ICPC 2013 Ukraine Central Contest.
0
hOlyNeKo
0 / 0 / 1
Регистрация: 18.04.2013
Сообщений: 20
20.04.2013, 20:45 #8
Могу предположить, что необходимо после прибавления очередного остатка находить остаток деления суммы на 10^9+7. Тогда переполнения точно не будет.
0
dr.curse
392 / 348 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 20:52 #9
а папробуйте решить ее циклами так
берем прогрессию где d=a считаем сумму элементов меньших n обозначим сумму черес s_a
тоже для d=b - s_b и d=a+b - s_ab
ответом будет s_a+s_b-s_ab

Добавлено через 1 минуту
Цитата Сообщение от hOlyNeKo Посмотреть сообщение
Могу предположить, что необходимо после прибавления очередного остатка находить остаток деления суммы на 10^9+7. Тогда переполнения точно не будет.
какое переполнение? тут проблемы со временем, там n слишком большое и с O(n) алгоритмом ее не решить
0
ValeryS
Модератор
6961 / 5298 / 522
Регистрация: 14.02.2011
Сообщений: 17,865
20.04.2013, 20:53 #10
Цитата Сообщение от A1exSun Посмотреть сообщение
Может я уже не соображаю, но не пойму что вы мне предлагаете.
примерно так сумма
чисел делящихся на A
C++
1
2
for(int i=A; i<n;i+=A)
 Summ+=i;
это сумма арифметической прогрессии
которая равна сумме первого и последнего элемента умноженное на количество элементов и деленное на два

значит нужно узнать последний член прогрессии
C++
1
int last=(n/A)*A;
и количество
C++
1
int m= (A+last)/A;
сумма равна
C++
1
Sum=((A+last)*m)/2;
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 20:55  [ТС] #11
Цитата Сообщение от aram_gyumri Посмотреть сообщение
а папробуйте решить ее циклами так
берем прогрессию где d=a считаем сумму элементов меньших n обозначим сумму черес s_a
тоже для d=b - s_b и d=a+b - s_ab
ответом будет s_a+s_b-s_ab
Напишите код пожалуйста, а то не совсем понятно.
3 цикла? Не выиграет же время.

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
примерно так сумма
чисел делящихся на A
C++
1
2
for(int i=A; i<n;i+=A)
 Summ+=i;
это сумма арифметической прогрессии
которая равна сумме первого и последнего элемента умноженное на количество элементов и деленное на два

значит нужно узнать последний член прогрессии
C++
1
int last=(n/A)*A;
и количество
C++
1
int m= (A+last)/A;
сумма равна
C++
1
Sum=((A+last)*m)/2;
Так это только для A, а нужно сумму элементов которые делятся A или B, к тому же без повторов.
Так как в примере - 6 учитывается лишь раз, а не 2 (делиться и на 2 и на 3).
0
ValeryS
Модератор
6961 / 5298 / 522
Регистрация: 14.02.2011
Сообщений: 17,865
20.04.2013, 21:11 #12
наврал по формулам
количество элементов
C++
1
int m=n/A;
последний элемент
C++
1
int last=m*A;
Добавлено через 5 минут
Цитата Сообщение от A1exSun Посмотреть сообщение
Так это только для A, а нужно сумму элементов которые делятся A или B,
так для B по той же схеме посчитай другую сумму
Цитата Сообщение от A1exSun Посмотреть сообщение
к тому же без повторов.
насчет повторов ты ничего не говорил
хорошо рассчитываем третью сумму
где первый член
A*B
количество
n/(A*B)
последний элемент
(n/(A*B))*(A*B)
потом складывай две суммы и вычитай третью
C++
1
summ=summA+summB-summAB;
Добавлено через 8 минут
да кстати в общей формуле есть исключение
если первый элемент равен последнему то это не прогрессия и сумма равна элементу
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 21:11  [ТС] #13
Цитата Сообщение от ValeryS Посмотреть сообщение
насчет повторов ты ничего не говорил
хорошо рассчитываем третью сумму
где первый член
A*B
количество
n/(A*B)
последний элемент
(n/(A*B))*(A*B)
потом складывай две суммы и вычитай третью
C++
1
summ=summA+summB-summAB;
В первом посту все описано.
Много действий, опять же. Мой алгоритм проще и быстрее. А надо еще быстрее.
0
ValeryS
Модератор
6961 / 5298 / 522
Регистрация: 14.02.2011
Сообщений: 17,865
20.04.2013, 21:12 #14
ну тут и по количеству(1) можно посмотреть
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 216
20.04.2013, 21:13  [ТС] #15
В общем, напиши лучше код. А то я мало понимаю твое мышление.
0
20.04.2013, 21:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 21:13
Привет! Вот еще темы с ответами:

Найти сумму натуральных чисел, которые делятся на 5 и не делятся на m - C++
Из первых n натуральных чисел найдите сумму тех из них, которые делятся на 5 и не делятся на m (m&lt;n). Натуральные значения n и m введите с...

Напечатать те из двузначных чисел, которые делятся на 4, но не делятся на 6 - C++
Доброго времени суток ! Помогите решить задачу ! Нужно написать в цикле с предисловием следующее : Напечатать те из двузначных чисел,...

Напечатать те из двузначных чисел, которые делятся на 4, но не делятся на 6 - C++
. Напечатать те из двузначных чисел, которые делятся на 4, но не делятся на 6. С++ VS

Олимпиадная задача Сумма простых - C++
наприме мы вводим размер массива 3 потом сколько чисел надо сложить 2 а потом массив 6 5 7 и вы водитьса другой массив например 6+5=11...


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

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

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