Divisor Summation solution getting TLE

help
,
1

I wanted to solve this problem and getting TLE.

Here is my code,

#include <iostream>
#include <cassert>
#include <vector>
#include <numeric>
using namespace std;

int main(){
    int test_case;
    vector<int> divisors;

    scanf("%d", &test_case);
    assert(test_case <= 200000);

    while(test_case--) {
        int number;
        scanf("%d", &number);
        assert(number >= 1);
        assert(number <= 500000);

        int half_number = number / 2;
        for(int i = 1; i <= half_number; i++) {
            if(number%i == 0 && i != number) {
                divisors.push_back(i);
            }
        }

        printf("%d\n", accumulate(divisors.begin(), divisors.end(), 0));
        divisors.clear();
    }

    return 0;
}
1 Like
2

Can you fix the link? Otherwise it is hard to check whether the problem is part of an active contest or not.
Links in markdown have the form
[text](url)
The url is probably missing. At the bottom of your post you should see a pencil button, clicking that you can edit your question.

3

Now I fixed it… @spaanse

4

You can predict that your algorithm would get TLE:

Your algorithm is \mathcal O(tn) where t is the number of testcases and n is the value of the given integer. Filling in the maximum values of both of these we get that your algorithm would need roughly 500\;000\cdot200\;000=100\;000\;000\;000=10^{11} operations. A handy guideline is that a computer can perform 10^9 operations per second, so your program would take 100s in the worst case, giving TLE.

This means you need a better algorithm to pass the time limit.
To give you a hint:

Hint

If 3 divides 33, what does that say about 11?