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

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

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

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

20.04.2013, 18:22. Просмотров 1471. Ответов 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 мс

Как еще больше оптимизировать?
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 целыми числами, полученными с помощью генератора случайных чисел. Найти среди компонентов файла количество чисел, которые...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
20.04.2013, 21:22 #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#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:27  [ТС] #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
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:28 #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#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:32  [ТС] #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 минуты
У меня были проблемы со вторым тестом, когда я учитывал последний элемент последовательности (в общем, <= вместо < в цикле).
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
20.04.2013, 21:32 #20
Цитата Сообщение от A1exSun Посмотреть сообщение
Неверный ответ на втором тесте.
вполне возможно писал на коленке
какие данные
напиши проверю
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:33 #21
а так?
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main()
{
    long long n,a,b,sa,sb,sab,c,cc;
    scanf("%lld%lld%lld",&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("%lld",sa+sb-sab);
    return 0;
}
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:35  [ТС] #22
Цитата Сообщение от ValeryS Посмотреть сообщение
вполне возможно писал на коленке
какие данные
напиши проверю
А рапортов нет... Вот в чем вся прелесть олимпиадных задач
Помню, 150 6 7 должно давать 3315. Руками утром считал.

Добавлено через 1 минуту
Цитата Сообщение от aram_gyumri Посмотреть сообщение
а так?
То же самое.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
20.04.2013, 21:35 #23
Цитата Сообщение от A1exSun Посмотреть сообщение
У меня были проблемы со вторым тестом, когда я учитывал последний элемент последовательности (в общем, <= вместо < в цикле).
стоп а если N делится на A (B) то так и будет
тогда нужно сделать так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 int summA,int summB,int summAB,summ;
int qA=n/A;
if(n%A==0)
 qA--;
int lastA =qA*A;
summA=((A+lastA)*qA)/2;
 
int qB=n/B;
if(n%B==0)
 qB--;
int lastB =qB*B;
summB=((B+lastB)*qB)/2;
 
int qAB=n/(A*B);
if(n%(A*B)==0)
 qAB--;
int lastAB =qAB*A*B;
summAB=((A*B+lastAB)*qAB)/2;
 
summ=summA+summB-summAB;
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:35 #24
у меня правильный ответ выдает на твой тест
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:37  [ТС] #25
Цитата Сообщение от aram_gyumri Посмотреть сообщение
у меня правильный ответ выдает на твой тест
Да я уже проверил, сходится...
Не знаю в чем прикол. У меня было когда лишнее считал.
Мой код проходит 53 теста, снова проверял чтоб убедиться не сломалось ли ничего там.
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:38 #26
Цитата Сообщение от ValeryS Посмотреть сообщение
стоп а если N делится на A (B) то так и будет
тогда нужно сделать так
да действительно а я просто из всех 1 вычитал поскольку проверял только тест 10 2 5
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
20.04.2013, 21:59 #27
вот код
объеденены два подхода твой и мой

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
 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<<endl;
    cout<<(sum % 1000000007)<<endl;
  long long summA,summB,summAB,summ;
 long long qA=n/a;
if(n%a==0)
 qA--;
 long long lastA =qA*a;
summA=((a+lastA)*qA)/2;
 
 long long qB=n/b;
if(n%b==0)
 qB--;
 long long lastB =qB*b;
summB=((b+lastB)*qB)/2;
 
 long long qAB=n/(a*b);
if(n%(a*b)==0)
 qAB--;
 long long lastAB =qAB*a*b;
summAB=((a*b+lastAB)*qAB)/2;
 
summ=summA+summB-summAB;
 
 cout<<(summ % 1000000007)<<endl;   
 return 0;
}
а вот ответы
первый твой второй мой
6000
2
3

11997000
11997000
150
7
6

3165
3165
7
2
3

15
15
как видишь равны
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
20.04.2013, 22:07 #28
valerys,aram, там числа очень большие могут быть и суммы не влезут в long long
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 22:13  [ТС] #29
Цитата Сообщение от ValeryS Посмотреть сообщение
а вот ответы
первый твой второй мой

как видишь равны
Я не знаю, почему мой код проходит, твой нет. Позже может быть дадут логи проверок, там видно будет.

Добавлено через 24 секунды
Цитата Сообщение от ya_noob Посмотреть сообщение
valerys,aram, там числа очень большие могут быть и суммы не влезут в long long
У меня же влезли.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
20.04.2013, 22:19 #30
Цитата Сообщение от ya_noob Посмотреть сообщение
valerys,aram, там числа очень большие могут быть и суммы не влезут в long long
а в тупом цикле влезут???
самое большое что может быть это число 10^18 A=1
тогда сумма будет где то 10^36

и вообще я идею дал думайте сами

Добавлено через 2 минуты
Цитата Сообщение от A1exSun Посмотреть сообщение
Я не знаю, почему мой код проходит, твой нет.
А ты уже правленый пробовал??
в смысле с учетом того что N кратное A(B)?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 22:19
Привет! Вот еще темы с ответами:

Найти сумму натуральных чисел, которые делятся на 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...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.04.2013, 22:19
Ответ Создать тему
Опции темы

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