### SPyofgame's blog

By SPyofgame, history, 5 weeks ago, ,

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 weeks ago, # | ← 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 weeks ago, # ^ |   0 Thanks <3But if there is just one query, can I approach faster than O(√(n)) ?
•  » » 5 weeks ago, # ^ |   0 Why I cant see your ideone code ?
•  » » » 5 weeks ago, # ^ |   0 Weird. It should be visible.
•  » » » » 5 weeks ago, # ^ |   0 Can you show me the source code or pseudo code ?
•  » » » » » 5 weeks ago, # ^ |   +2 Code#include using namespace std; const int MAXN = 20005; vectordivisors[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 "<
•  » » » » » » 5 weeks ago, # ^ |   +1 oh, ok thanks <3We 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); 
•  » » » » » » » 5 weeks ago, # ^ |   +1 Yes.
 » 5 weeks ago, # | ← 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 weeks ago, # ^ |   +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 weeks ago, # ^ |   +1 Right, 'reduces to factoring' would be a better way to phrase it.
•  » » 5 weeks ago, # ^ |   0 Sorry but I dont understand what is non-trivial divisor meaning. Is that mean I cant use the O(√(n)) approach ?
•  » » » 5 weeks ago, # ^ | ← 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 weeks ago, # ^ |   0 Any positive divisors right ?
•  » » » » 5 weeks ago, # ^ |   0 You mean like rho algorithms ?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 If the complexity is like that... Is there a possible happen where it has the worst case of log(n) ^ k would be far bigger than sqrt(n) right ?
•  » » 5 weeks ago, # ^ |   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 ?