Nayem.'s blog

By Nayem., history, 4 weeks ago, In English,

I was trying to solve this problem

let, int moded = x % A here, the highest value of moded can be A-1;

but if we add some other numbers.. then.. (x % A1) + (x % A2) + .... + (x % An) then what can be the highest result if we add all the moded from Ai to An for this sequence?

for each Ai, if we take Ai-1, then the result will be maximum, but will there always exist an x if we were to get this maximum result?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

There always exists such $$$m$$$.
Copy pasting from editorial.
Let $$$m=a_1*a_2...a_n$$$
Then $$$m-1$$$ is the required $$$x$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. From what you said, I figured maybe x = lcm(a1, a2, ..., aN) — 1

    but how x = (a1∗a2...aN) — 1 ?

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      it can be any multiple of LCM.

      let say [3 4 6]

      you will get same remainder from X=lcm(3,4,6)-1 or X=3*4*6-1