TuHoangAnh's blog

By TuHoangAnh, history, 3 years ago, In English

given an integer $$$n$$$, find the number of $$$(i,j,k)$$$ so that:

$$$1<i<j<k<=n$$$.

$$$i*j*k$$$ is a perfect square.

$$$3<n<=10^5$$$

  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Im dumb so pls don't take this seriously though. I can now think of a O(N*sqrt(N)) solution, would it be exceeded time limit cause u did not mention the time.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the time limit 1.5s

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      well, 1e5*1e3=1e8 (could be less) might still get the job done.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would probably be okay even with just 1 second TL, $$$n$$$ is only $$$10^5$$$, not even $$$2 \cdot 10^5$$$ or something.