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

Оптимизация простой программы - C++

Восстановить пароль Регистрация
 
Why so seriouS
 Аватар для Why so seriouS
44 / 44 / 1
Регистрация: 12.03.2013
Сообщений: 167
21.04.2013, 13:56     Оптимизация простой программы #1
Суть задачи такова: программа должна вычислить сумму цифр которые делятся на a или b и цифры должны быть меньше n. Максимальное число n = 10^18. Программа работает хорошо но вылетает на тесте тайм лимит. Как ее можно оптимизировать?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long long int n,a,b;
    
    cin>>n>>a>>b;
    unsigned long long  int tmp = 0;
    for(int i = 1; i < n; i++)
    {
    if((i%a == 0) || (i%b == 0)){
            tmp += i;
            }
    }
    cout<<(tmp%1000000007);
    
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 13:56     Оптимизация простой программы
Посмотрите здесь:

C++ Оптимизация кода программы
C++ Оптимизация программы на С++
Оптимизация программы C++
Оптимизация программы C++
Оптимизация программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hommius
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 12
21.04.2013, 14:05     Оптимизация простой программы #2
как вариант способа найти сумму:
C++
1
2
int x = lcm(a,b);
for(int i = x; i<n; i+=x) tmp+=i;
lcm - функция нахождения наименьшего общего кратного
SummerRain
 Аватар для SummerRain
325 / 324 / 17
Регистрация: 16.12.2012
Сообщений: 544
21.04.2013, 14:05     Оптимизация простой программы #3
найди наименьшее общее кратное чисел a и b.
И пройдись по циклу от одного до n с шагом HOK(a, b).
Tiva
94 / 94 / 1
Регистрация: 25.04.2012
Сообщений: 429
21.04.2013, 14:06     Оптимизация простой программы #4
не знаю, оптимизация это или нет, но зачем за такой простой программой тащить весь std неймспейс?
C++
1
2
std::cout...
std::cin
или
C++
1
2
using std::cout;
usint std::cin;
в цикле i тоже можно сделать unsigned
но это мелочи, думаю сильно не повляют))
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.04.2013, 16:24     Оптимизация простой программы #5
Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Yandex
Объявления
21.04.2013, 16:24     Оптимизация простой программы
Ответ Создать тему
Опции темы

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