Need Help on Modular Arithmetic question

Правка en2, от ankurrathinsit, 2020-05-03 03:52:42

Suppose we are given number N we have to find a number M less than N such that M*M when divided by N gives maximum remainder . Also value of M should be maximum possible ( nearest to N).


It is given that all computed values are within integer range. for e.g : N=15

maximum remainder is obtained from M=5 and M=10

so M = 10 is the answer.


I could only formulate the naive solution for it which works in O(N) time complexity. Any better approach for this ??

Теги #modular arithmetic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ankurrathinsit 2020-05-03 03:52:42 41
en1 Английский ankurrathinsit 2020-05-03 03:45:04 533 Initial revision (published)