I was trying to solve this bugaboo on SPOJ.

My approach is fairly simple. I pre-calculate all prime numbers, smallest prime factor, and all divisors in sieve() first.

Then for each i in [1,maxN) I calculate the number of divisors for each 'i' and verify if its a valid number in O(1).

total complexity is : O(N log(log N))) for sieve + O(N log(N) to check number of divisors

My solution which TLE'd.

I'm not able to figure out what I'm missing here. Can someone please help me with this?

Thanks!

I was solving this.

I encountered a problem while using std::accumulate.

I noticed that accumulate(v.begin(), v.end(), 0L) behaves differently in sublimText/Ideone and Codeforces.

for example,

int main() {
vector<long long> v{1,-1000000000,1,-1000000000,1,-1000000000};
long long sum = accumulate(v.begin(), v.end(), 0L);
cout<<sum;
}

in sublimeText or Ideone: prints -2999999997 and in Codeforces prints 1294967299.

you can try running this here

AC solution

Wrong solution

however, when 0L is changed to 0LL in accumulate function, both sublime text and CF returns the right sum (-2999999997)

is this expected? can someone help me understand this weird behavior?

Hi All,

I was trying to solve this using Dijkstra.

Solution here.

I'm getting TLE in the last few test cases. Can someone suggest me any further optimizations I can make?

thanks! have a good day!

Till yesterday I was using static version of a20j.

And today morning I was surprised to see contests in it. Old a2oj is back!

If this is old news sorry for duplicate post!