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

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

Question: Given two positive numbers N and M, find minimal |c — M| where N mod c = 0

Can we solve this problem in O(log (n)) or faster ?

Here is my approach in O(sqrt(n))

My code

Sorry for my bad English ;-;

If I have wrong something, please tell me. It is better to do that than just downvote me because I and someone will learn many new things <3

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

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

If you preprocess divisors for all numbers ( reference: code $$$O(NlogN)$$$ ), then you have vector $$$divisors[N]$$$, and you can binary search for $$$M$$$ in that vector ( even iterating through the array is good enough, because there are very few divisors link ).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks <3

    But if there is just one query, can I approach faster than O(√(n)) ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why I cant see your ideone code ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Weird. It should be visible.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you show me the source code or pseudo code ?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          Code
          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            oh, ok thanks <3

            We can use this as sieve right ?

            Sieve
»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

If I pick $$$M = \lfloor N/2 \rfloor$$$, finding such a $$$c$$$ is equivalent to finding a non-trivial divisor, so your problem is at least as hard as factoring.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Wouldn't it be "at least as hard as factoring"? Or is the answer somehow obvious if you have the factoring (I can't see why it is)?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry but I dont understand what is non-trivial divisor meaning. Is that mean I cant use the O(√(n)) approach ?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You can use the $$$O(\sqrt{n})$$$ approach, I'm saying you can't (hope to) do better than that, since solving your problem in $$$O(\log n)$$$ time means solving prime factorization in that time.

      By 'non-trivial divisor' of $$$N$$$ I mean any divisor that is not $$$1$$$ or $$$N$$$ itself. It should be clear that if $$$N$$$ has any non-trivial divisors, they will be closer to $$$\lfloor N/2 \rfloor$$$ than the trivial divisors $$$1$$$ and $$$N$$$ are. Therefore, we could factorize any $$$N$$$ by finding this closest divisor $$$d$$$ -- if it is $$$1$$$ (or $$$N$$$) then $$$N$$$ is prime, if it is not, then we recursively factorize $$$d$$$ and $$$N/d$$$.

      EDIT: To add to this, it is an open problem whether factoring can be solved in $$$O(\log^k n)$$$ time for some $$$k$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you pick M = ⌊N/2⌋ is that mean the closest divisor c is N / fp where fp is the smallest prime divisor of N ?