Quote:
I got TLE in UVA. It was obvious to get TLE.
This problem is worded the way of challenges sites,
you need to know the strait forward solutions (or brute force) are never the solution.
You need to have deep understanding of the problem in order to apply algorithm simplifications and make your solution faster.
In this code, for any
N
, you loop
N
times: O(N)=N
for(int i=1; i<=n; i++) {
In this code, for any
N
, you loop
√N
times: O(N)=√N
for(int i=1; i*i<n; i++) {
But there is a multiplication on every loop.
In this code,
√N
multiplications are replace by a single square root function.
Top=int(sqrt(N)
for(int i=1; i<=Top; i++) {
You need to take advantage of any possible shortcut in you code:
Everytime you find a divisor
i
of
N
, it imply that
N/I
is also a divisor of
N
, without further checking.
This code:
if(n%i==0 && i%k!=0)sum+=i;
if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);
translate as
if(n%i==0 ){
if(i%k!=0)sum+=i;
if((n/i)%k!=0)sum+=(n/i);
}
And there is more to find.
You also may want to play with the list of prime factors of the number.