BL7A.'s blog

150A — Win or Freeze

By BL7A., history, 6 years ago, In English

I was trying to solve 150A and I submitted a solution where I used a variable ( i ) in a loop : 

for(int i=2; i*i<=n; i++)
    {
        while(n%i == 0)
        {
            n /= i;
            p[k++] = i;
        }
    }

and it got TLE in test 7

submission : 32983991

and when I changed the datatype of variable ( i ) to long long it got accepted.

submission : 32984272

can anyone help me with the reason...?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When "i" is an int, the calculation "i*i" will result in an overflow, producing a negative number, which will always be less than "n". It gets TLE because of the infinite loop...

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

the limit on n is 1013. i is an integer, and it cannot be higher than 231 - 1, so it will never exceed n if n is high enough. You basically ran an infinite loop.

Edit: I was too late :P

→ Reply