sourav_malo's blog

Extended B (Educational Codeforces Round 54)!!
By sourav_malo, history, 6 years ago, In English

As you know that Educational Codeforces Round 54 (Rated for Div. 2) was held yesterday. Perhaps, you solved 1076B - Divisor Subtraction without any difficulty. Now, I am thinking how to solve this problem if there are no less than 10^5 queries. Please, mention the complexity with approach.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

owowow

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

if you lower the limit of n to 1e7 than you can have as many queries as you want, but i dont think 1e10 is gonna do well for more than 100 queries...

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

    There are around 1e4 primes lesser than 1e5 so you can optimize it to work for around 1e4 queries (and maybe faster with pollard rho?)

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

      That is impossible to do so in time limit of 2 or 3 seconds, isn't it?

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

        A simple 1e8 loop runs under 1 second easily in codeforces.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has there any way to find at least a divisor of n smaller than sqrt(n) within at most 1000 loops where n<=10^10?

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

    Isn't this question equivalent to integer factorization at the worst case? Then, I suppose there are no known way to do the task in 1000 loops...

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

      I thaught that also...whatever,thanks bro....

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

        As tfg mentioned above, for a lot of queries, to precompute all the primes in range [2, 1e5] would be fastest. Then your task must cost at most which is larger than 1000

        → Reply