### _jarvis_'s blog

By _jarvis_, history, 5 years ago,  spoj,
By _jarvis_, history, 5 years ago, i tried to google regarding this doubt but there was no specific clarification, first i would state the theoram, then i will ask the doubt

Theoram

according to my understanding, chinese remainder theoram is stated as,

for some number x, if we want to find x % M,

where M = m1*m2....*mr , (all mi being relatively prime to each other)

then we may do it as,

if x = ai(mod mi)

then x%M = a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr)

where bi*(M/mi) = 1(mod mi)

DOUBT

1)i just wanted to know that can bi be fractional or it has to an integer value ? [got cleared answer is Integer only]

2)what if the sum

a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr)

exceeds M? (or are we sure it would always be less then M)

Read more » By _jarvis_, history, 5 years ago, I was solving a problem on spoj, the solution of that problem requires the assumtion that,

if we add the absolute value of 2 or more linear equation in x ( eg. f(x)=|5x-8| + |7x-1| + |12x-13| ) then it necessary that f(x) (note:here f(x) denotes the sum of those terms) would be montonically increasing as we go way from the optimal value of x (note: optimal value of x is the value at which f(x) is minimum) .

Just wanted to confirm if that statement is true or not?

Read more » 