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

inverse of euler's function
Автор nerd, 13 лет назад, По-русски

Please Help!


phi(N) = euler's function = x

how we can find N, when we are given x. let's name it like phi_inv(x) = N

for example: 

phi_inv(4) = 5, because phi(5) = 4.

x ≤ 1010
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
I don't know. It is really an interesting problem.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
φ(4) = 2, φ(3) = 2 you find any solution or all solutions ? 
→ Ответить
13 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
φ(4) = 2, φ(3) you find any solution or all solutions?

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I have solved this problem and find all answers if N <  = 1018 and used dp and factorization of N. But my classmates used brute-force with pruning and got AC ;)firstly need to determine what could be simpler in the decomposition of N.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      firstly, thanks!
      but, secondly, ii couldn't catch you as well, where is link to this problem and have you save all phi(i), where i = 1..1018 or something else. i couldn't catch you as well. could you be more specific?!
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        1. find all prime p satisfying n%(p - 1) =  = 0 
        2. sort all primes and run brute-force go(x), for every prime p bust α N = pα * q and run go(x / (pα - pα - 1))
        3. optimization many optimization
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
is this problem from SPOJ (or Project Euler)?

write n in form of p_i ^ e_i, and we should have p_1 < p_2 < ... and e_1 >= e_2 >= ..., then factor n and use depth first search to get the answer?

i am not just sure i have solved the problem...
→ Ответить