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

How do I solve the problem http://acm.timus.ru/problem.aspx?space=1&num=1673 ?

Автор some_random_handle, история, 9 лет назад, По-английски

Problem : http://acm.timus.ru/problem.aspx?space=1&num=1673

Through Discussion forum I found that it can be solved using Euler Totient Function. I have tried for 24 hours but couldn't understand the reason behind using Euler Totient function for this problem.

I feel glad if someone can explain me with the approach to the problem.

Thanks in advance.

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

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

We can see that the ith student takes part in the exams with id which are multiples of i.

think the question in the opposite way.

if there exists a student with id of x ,which gcd(x,n) > 1 then there exists a multiple of n which is also a multiple of x and smaller than n * n(x < n)

we can see that the multiples of x here is smaller then n,so that this student won't be admitted.

now that we've proved only students with id relatively prime to n will be admitted,so the total amount of students is the phi(n).

here exactly k students managed to be admitted,so we just need to find the minimal n which satisfies phi(n) = k

Hope it helps:)

→ Ответить