Блог пользователя _Body

interactive number theory problem
Автор _Body, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

This is an EOI problem ;).

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraint on x?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить