Форум программистов, компьютерный форум 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++ Олимпиадная задача Сумма простых
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:33     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:35  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #22
Цитата Сообщение от ValeryS Посмотреть сообщение
вполне возможно писал на коленке
какие данные
напиши проверю
А рапортов нет... Вот в чем вся прелесть олимпиадных задач
Помню, 150 6 7 должно давать 3315. Руками утром считал.

Добавлено через 1 минуту
Цитата Сообщение от aram_gyumri Посмотреть сообщение
а так?
То же самое.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
20.04.2013, 21:35     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:35     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #24
у меня правильный ответ выдает на твой тест
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 21:37  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #25
Цитата Сообщение от aram_gyumri Посмотреть сообщение
у меня правильный ответ выдает на твой тест
Да я уже проверил, сходится...
Не знаю в чем прикол. У меня было когда лишнее считал.
Мой код проходит 53 теста, снова проверял чтоб убедиться не сломалось ли ничего там.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
20.04.2013, 21:38     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #26
Цитата Сообщение от ValeryS Посмотреть сообщение
стоп а если N делится на A (B) то так и будет
тогда нужно сделать так
да действительно а я просто из всех 1 вычитал поскольку проверял только тест 10 2 5
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
20.04.2013, 21:59     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #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
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
20.04.2013, 22:07     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #28
valerys,aram, там числа очень большие могут быть и суммы не влезут в long long
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 22:13  [ТС]     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #29
Цитата Сообщение от ValeryS Посмотреть сообщение
а вот ответы
первый твой второй мой

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

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

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

Добавлено через 2 минуты
Цитата Сообщение от A1exSun Посмотреть сообщение
Я не знаю, почему мой код проходит, твой нет.
А ты уже правленый пробовал??
в смысле с учетом того что N кратное A(B)?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.04.2013, 22:25     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #31
Как-то так, по формуле включений-исключений.
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
#include <iostream>
 
int foo(long long x, long long n, int modulo)
{
    long long first = x;            //первый член арифметической прогрессии
 
    long long last = (n / x * x);   //последний член арифметической прогресии
 
    long long count  = n / x;       //количество членов в арифметической прогрессии
 
    return ( ( ( (first % modulo + last % modulo) % modulo) * (count % modulo) ) / 2 ) % modulo;
}
 
int main()
{
    const int modulo = 1000000007;
    
    long long n;
 
    std::cin >> n;
    
    long long a, b;
    
    std::cin >> a >> b;
 
    std::cout << (foo(a, n, modulo) - foo(a * b, n, modulo) + foo(b, n, modulo)) % modulo << std::endl; 
}
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
20.04.2013, 22:38     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #32
valerys, переполнение это одна из проблем. что касается неправильного резульрата, то попробуйте протестировать свою программу при а=2 и b=4. что получится?

Добавлено через 6 минут
вычитать нужно не сумму для a*b, а сумму для нок(аb)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.04.2013, 22:43     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #33
Цитата Сообщение от ya_noob Посмотреть сообщение
вычитать нужно не сумму для a*b, а сумму для нок(аb)
Кстати да, тут я поспешил.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
20.04.2013, 22:49     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #34
Цитата Сообщение от ya_noob Посмотреть сообщение
valerys, переполнение это одна из проблем. что касается неправильного резульрата,
не надо мне за переполнения рассказывать
я тебя спрашивал почему здесь

Цитата Сообщение от ValeryS Посмотреть сообщение
summA=((a+lastA)*qA)/2;
Будет переполнение
а здесь
Цитата Сообщение от A1exSun Посмотреть сообщение
for (long long i = b; i < n; i += b) sum += i;
нет?


Цитата Сообщение от ya_noob Посмотреть сообщение
вычитать нужно не сумму для a*b,
это я уже понял на тесте 123 12 15

Цитата Сообщение от ya_noob Посмотреть сообщение
а для нок(аb)
не совсем нок
нок дла 12 и 15 =3
а вычитать нужно 60 и 120
т.е
сумма должна быть для такого ряда
A*B/нок ........ (A*B/нок)*k;
сейчас думаю как быстро найти нок

Добавлено через 1 минуту
diagon, да я тоже в это вперся
как то числа были заданы 3 2 и 6 7
у них нет общих делителей
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
20.04.2013, 22:56     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #35
я всё правильно написал, именно нок, а вы путаете его с нод
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.04.2013, 23:00     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #36
С учетом того, что пересечением является нок, будет как-то так
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
39
40
#include <iostream>
 
int foo(long long x, long long n, int modulo)
{
    long long first = x;            //первый член арифметической прогрессии
 
    long long last = (n / x * x);   //последний член арифметической прогресии
 
    long long count  = n / x;       //количество членов в арифметической прогрессии
 
    return ( ( ( (first % modulo + last % modulo) % modulo) * (count % modulo) ) / 2 ) % modulo;
}
 
template <class T>
T gcd(T a, T b)
{
    while (a ^= b ^= a ^= b %= a);
    return b;
}
 
template <class T>
T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}
 
int main()
{
    const int modulo = 1000000007;
    
    long long n;
 
    std::cin >> n;
    
    long long a, b;
    
    std::cin >> a >> b;
 
    std::cout << (foo(a, n, modulo) - foo(lcm(a, b), n, modulo) + foo(b, n, modulo)) % modulo << std::endl; 
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
20.04.2013, 23:05     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #37
вот исправленая версия
тестируйте
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "stdafx.h"
#include <iostream>
 
using namespace std;
long long NOK(long long A,long long B)
{
if(A%2==0&&B%2==0)
 return 2;
long long c=A;
if(A>B)
  c=B;
for(int i=3;i<c/2;c+=2)
{
 if(A%i==0&&B%i==0)
     return i;
}
return 1;
 
 
}
 
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 nok=NOK(a,b); 
long long first=a*b/nok;
 
long long qAB=n/first;
if(n%first==0)
 qAB--;
long long lastAB =qAB*first;
summAB=((first+lastAB)*qAB)/2;
 
summ=summA+summB-summAB;
 
 cout<<(summ % 1000000007)<<endl;   
 return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
я всё правильно написал, именно нок, а вы путаете его с нод
ну попутал с кем не бывает
я твоего варианта не вижу

Добавлено через 1 минуту
diagon,
проверь свой вариант
если A равно B
мой врет
причем оба метода
я так понимаю 0 должен быть
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 23:10     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
20.04.2013, 23:10     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B #38
я с телефона пишу. думаю на набор программы вся ночь уйдет
Yandex
Объявления
20.04.2013, 23:10     Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Ответ Создать тему
Опции темы

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