Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 18:22     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #1
Условие
Ватсон поставил Рыбке простую задачу - найти сумму чисел меньших 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 мс

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

Найти среди компонентов файла количество чисел, которые делятся на 2, но не делятся на 4 C++
нужно написать программу, находящую количество чисел меньших x, которые делятся в точности на три простых числа. C++
C++ Определить кол-во чисел <n, которые не делятся на 11
Напечатать те из двузначных чисел, которые делятся на 4, но не делятся на 6 C++
C++ Олимпиадная задача Сумма простых
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
20.04.2013, 19:18     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #2
числа, делящиеся на (а) - арифметическая прогрессия; числа, делящиеся на (в) - арифметическая прогрессия; числа, делящиеся на (а и в) - арифметическая прогрессия...
разбейте на куски так, чтобы ответ не переполнял тип, и будьте счастливы.
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 19:20  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #3
Цитата Сообщение от salam Посмотреть сообщение
разбейте на куски так, чтобы ответ не переполнял тип, и будьте счастливы.
Что разбить на куски?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
20.04.2013, 20:36     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #4
высчитаете сумму арифметической прогрессии от 1 до N. если будете считать так, что тип переполнится, ибо N <= 10^18. поэтому поделите прогрессию на несколько частей и для каждой считайте ответ.
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 20:39  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #5
Цитата Сообщение от salam Посмотреть сообщение
высчитаете сумму арифметической прогрессии от 1 до N. если будете считать так, что тип переполнится, ибо N <= 10^18. поэтому поделите прогрессию на несколько частей и для каждой считайте ответ.
Может я уже не соображаю, но не пойму что вы мне предлагаете.
Мой код в 1 сообщении полностью рабочий, но он не прошел 53-ю проверку системы - превысил лимит времени выполнения в 500 мсек. И я спрашиваю как его еще больше оптимизировать...
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 20:42     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #6
A1exSun, а можно ссылку на задачу?
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 20:44  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #7
Цитата Сообщение от aram_gyumri Посмотреть сообщение
A1exSun, а можно ссылку на задачу?
Не получится, система закрыта. Только для своих
Это с ICPC 2013 Ukraine Central Contest.
hOlyNeKo
0 / 0 / 1
Регистрация: 18.04.2013
Сообщений: 20
20.04.2013, 20:45     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #8
Могу предположить, что необходимо после прибавления очередного остатка находить остаток деления суммы на 10^9+7. Тогда переполнения точно не будет.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 20:52     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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) алгоритмом ее не решить
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
20.04.2013, 20:53     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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;
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 20:55  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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).
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
20.04.2013, 21:11     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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 минут
да кстати в общей формуле есть исключение
если первый элемент равен последнему то это не прогрессия и сумма равна элементу
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:11  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #13
Цитата Сообщение от ValeryS Посмотреть сообщение
насчет повторов ты ничего не говорил
хорошо рассчитываем третью сумму
где первый член
A*B
количество
n/(A*B)
последний элемент
(n/(A*B))*(A*B)
потом складывай две суммы и вычитай третью
C++
1
summ=summA+summB-summAB;
В первом посту все описано.
Много действий, опять же. Мой алгоритм проще и быстрее. А надо еще быстрее.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
20.04.2013, 21:12     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #14
ну тут и по количеству(1) можно посмотреть
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:13  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #15
В общем, напиши лучше код. А то я мало понимаю твое мышление.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
20.04.2013, 21:22     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #16
Цитата Сообщение от A1exSun Посмотреть сообщение
Мой алгоритм проще и быстрее.
проще да
а быстрее???
сколько итераций циклов ты проведешь при числе 103 и делении на 2 и 3

Цитата Сообщение от A1exSun Посмотреть сообщение
Много действий, опять же.
Я и не настаиваю
можешь продолжать крутить циклы но не жалуйся что долго выходит

и где тут сложность
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 int summA,int summB,int summAB,summ;
int qA=n/A;
int lastA =qA*A;
summA=((A+lastA)*qA)/2;
 
int qB=n/B;
int lastB =qB*B;
summB=((B+lastB)*qB)/2;
 
int qAB=n/(A*B);
int lastAB =qAB*A*B;
summAB=((A*B+lastAB)*qAB)/2;
 
summ=summA+summB-summAB;
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:27  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #17
Цитата Сообщение от ValeryS Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 int summA,int summB,int summAB,summ;
int qA=n/A;
int lastA =qA*A;
summA=((A+lastA)*qA)/2;
 
int qB=n/B;
int lastB =qB*B;
summB=((B+lastB)*qB)/2;
 
int qAB=n/(A*B);
int lastAB =qAB*A*B;
summAB=((A*B+lastAB)*qAB)/2;
 
summ=summA+summB-summAB;
Неверный ответ на втором тесте. Логов нет.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:28     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #18
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main()
{
    int n,a,b,sa,sb,sab,c,cc;
    scanf("%d%d%d",&n,&a,&b);
    c=(n/a)*a;
    cc=(a+c)/a-1;
    sa=(a+c)*cc/2;
    c=(n/b)*b;
    cc=(b+c)/b-1;
    sb=(b+c)*cc/2;
    a=a*b;
    c=(n/a)*a;
    cc=(a+c)/a-1;
    sab=(a+c)*cc/2;
    printf("%d",sa+sb-sab);
    return 0;
}
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:32  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #19
Цитата Сообщение от aram_gyumri Посмотреть сообщение
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main()
{
    int n,a,b,sa,sb,sab,c,cc;
    scanf("%d%d%d",&n,&a,&b);
    c=(n/a)*a;
    cc=(a+c)/a-1;
    sa=(a+c)*cc/2;
    c=(n/b)*b;
    cc=(b+c)/b-1;
    sb=(b+c)*cc/2;
    a=a*b;
    c=(n/a)*a;
    cc=(a+c)/a-1;
    sab=(a+c)*cc/2;
    printf("%d",sa+sb-sab);
    return 0;
}
То же самое... Что-то вы не учли.

Добавлено через 2 минуты
У меня были проблемы со вторым тестом, когда я учитывал последний элемент последовательности (в общем, <= вместо < в цикле).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 21:32     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Еще ссылки по теме:

C++ Определит количество тех чисел, которые делятся на 7
C++ Найти сумму натуральных чисел, которые делятся на 5 и не делятся на m

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
20.04.2013, 21:32     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #20
Цитата Сообщение от A1exSun Посмотреть сообщение
Неверный ответ на втором тесте.
вполне возможно писал на коленке
какие данные
напиши проверю
Yandex
Объявления
20.04.2013, 21:32     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Ответ Создать тему
Опции темы

Текущее время: 14:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru