Closest Divisor of given number problems

Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

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

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

int f(int n, int m)
{
    int r = 1;
    int rt = sqrt(n);
    for (int i = 1; i <= rt; ++i)
    {
        if (n % i == 0)
        {
            int j = n / i;
            r = abs(r - m) < abs(j - m) ? r : j;
            r = abs(r - m) < abs(i - m) ? r : i;
        }
    }
    
    return r;
}

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

#asking, #algorithms, #complexity, #optimization

SPyofgame
7 лет назад
17

Комментарии (17)

Написать комментарий?

gupta_samarth

7 лет назад, скрыть # |

← Rev. 4 →

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

→ Ответить

SPyofgame

7 лет назад, скрыть # ^ |

Thanks <3

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

→ Ответить

SPyofgame

7 лет назад, скрыть # ^ |

Why I cant see your ideone code ?

→ Ответить

gupta_samarth

7 лет назад, скрыть # ^ |

Weird. It should be visible.

→ Ответить

SPyofgame

7 лет назад, скрыть # ^ |

Can you show me the source code or pseudo code ?

→ Ответить

gupta_samarth

7 лет назад, скрыть # ^ |

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;
vector<int>divisors[MAXN+5];

int main()
{
	for(int i=1;i<=MAXN;i++)
	{
		for(int j=i;j<=MAXN;j+=i)
		{
			divisors[j].push_back(i);
		}
	}

	int max_divisors = 0;
	for(int j=1;j<=MAXN;j++)
		max_divisors = max( max_divisors, (int)divisors[j].size() );
		
	cout<<"Maximum number of divisors of numbers upto "<<MAXN<<" are "<<max_divisors<<endl;	
	return 0;
}

→ Ответить

SPyofgame

7 лет назад, скрыть # ^ |

oh, ok thanks <3

We can use this as sieve right ?

Sieve

    cnt.assign(n + 1, 1);
    for (int i = 2; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            cnt[j]++;
    
    prime.assign(1, 2);
    for (int i = 3; i <= n; i += 2)
        if (cnt[i] == 2)
            prime.push_back(i);

→ Ответить

gupta_samarth

7 лет назад, скрыть # ^ |

Yes.

→ Ответить

TimonKnigge

7 лет назад, скрыть # |

← 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.

→ Ответить

-is-this-fft-

7 лет назад, скрыть # ^ |

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

→ Ответить

TimonKnigge

7 лет назад, скрыть # ^ |

Right, 'reduces to factoring' would be a better way to phrase it.

→ Ответить

SPyofgame

7 лет назад, скрыть # ^ |

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

→ Ответить

TimonKnigge

7 лет назад, скрыть # ^ |

← Rev. 2 →

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$$$.

→ Ответить