Divisor Summation solution getting TLE

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

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.

Now I fixed it… @spaanse

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?