serega.belarus's blog

Euler function
By serega.belarus, 12 years ago, translation, In English

Good day! I am trying to solve task 1673 from acm.timus.ru(click). I tried to solve this problem by the following way. 1) Firstly I precalculate the euler function for numbers from 1 till 2*10^5. 2) Then I start to search required value in array. But this solution has passed only 6 tests(in my version). In the 7th test It is needed to give answer for number which is more than 2*10^5 (2*10^9 is the max value of euler function in the problem). I want to know how we can quickly calculate argument of the euler if we know the value. My code(click)

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is the same problem I have.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is one DP method. Let DN — number of divisors of X. Let PN Number of primes p such that p — 1 is divisor of X. Note PN <= DN < 2000. int DP(int id_of_divisor, int primeNumberId). There is no more than PN * DN states and at each state you can use current prime number 0..log(X) times.

    → Reply