help with spoj problem

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

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

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

kingofnumbers
11 лет назад
6

Комментарии (5)

Показать архивные | Написать комментарий?

.o.

11 лет назад, # |

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.

→ Ответить

kingofnumbers

11 лет назад, # ^ |

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.

→ Ответить

.o.

11 лет назад, # ^ |

← Rev. 4 →

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.

→ Ответить

kingofnumbers

11 лет назад, # ^ |

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.

→ Ответить