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

Автор kingofnumbers, 12 лет назад, По-английски

Hi, I have no idea how to solve this problem. can anyone help me?

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

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

Every positive number can be represented as a form like this: 2^x * 3^y * z, where z is not divisible by 2 and 3.

Let's suppose that n = 2^x * 3^y * z. Then we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.

Now, let's define a plane P[z]. For each number 2^x * 3^y * z, draw a point in P[z]. Then, the problem will be solvable :)

Sorry for the poor English.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We can have 2n and 3n in set S if we didn't include n in set S.

    can you code your idea please to make me understand your idea very well.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry for my mistake..

      Let's suppose that n = 2^x * 3^y * z. (where z is not divisible by 2 and 3) If we include n in set S, we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.

      Let's define a plane P[z] where z is not divisible by 2 and 3. For each positive integer i = 2^x * 3^y * z (<= N), draw a point (x, y) at P[z].

      If we select the point (x, y) in P[z], then we cannot select the point (x+1, y) and (x, y+1) in P[z]. So the problem is: how many ways can we choose points such that the condition above is satisfied?

      The value of x and y are very small, so we can do this in DP.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Good idea, but how to do this in DP effectively, notice that we have n/3 numbers less than n that not divisible by 2 and 3 and we have 500 test cases per input.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You can use bitmasks.. It needs more complex solution than just bitmasking. Think about it :)