some_random_handle's blog

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

By some_random_handle, history, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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:)

→ Reply