Оптимизация вызова функции в циклах C++

Question

Имеется код

int func(int a, int b) {
    do {
        a /= b;
    } while (a % b == 0);
    return a;
}

int main(){
    ...
        for (int j=k; j <= n; j+=k){
            s += func(j, k);
        }
    ...
}

Программа ищет сумму чисел [1..n], 1 < n < 1 000 000 000. Причем, числа которые делятся на k должны быть заменены на "наименьший" делитель, например, 6 при k = 3 надо заменить на 2; 9 меняем на 1, т.к. 9 / 3 = 3 и 3 / 3 =1.

Возможно ли оптимизировать время выполнения данного участка кода. При n = 1000000000, k = 2, например, время выполнения > 1 сек, а ограничение 1 сек.

Answer 1

Никогда не пытайтесь ускорять код, не подумав о нормальном алгоритме...

unsigned long long func(unsigned long long n, unsigned long long k)
{
    if (n < k) return n*(n+1)/2;
    unsigned long m = n/k;
    return n*(n+1)/2 - k*m*(m+1)/2 +func(m,k);
}

Если не ошибаюсь, эта функция считает то, что вам надо - сумму чисел от 1 до n этих ваших "сокращенных" чисел...

БЛОГ НА HUSL

Оптимизация вызова функции в циклах C++

Ответы (1 шт):