_Body's blog

interactive number theory problem
By _Body, history, 3 years ago, In English

there is an unknown number x<=1000 and i want to find it i can ask two questions 1-number y and it will tell me if x is divisble by y 2-array and it will tell me if there is a number y in the array such that gcd(x,y)>1 it's true or false it won't tell what is the number

i can ask at most 40 questions i'm not able to do that in less than 190 queries

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

This is an EOI problem ;).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    i know i got it from there i got perfect score but i should't because of the cms thing that badawy put in the clarfication

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

Constraint on x?

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

Since, there can be atmost one prime factor greater than sqrt(x), we check for those below sqrt(x) which has upper bound in this case 31 and we have 11 primes till 31, so we can check for the highest power which divides x for each of these primes using 1st query type and binary search on the maximum possible power it can take (like 2 can have a maximum power of 9, so we binary search on 0 to 9). For checking if there is a prime factor greater than 31 make an array of the remaining primes (count = 157) and binary search on the prefix of this array that has an element say y, giving gcd(x,y)>1.

You can check all this will cost less than 40 queries. Further optimization will be that any x will have atmost 4 distinct prime factors, so you can optimize your binary search for primes less than sqrt(x) by just checking if that prime divides x or not

→ Reply