Is there an identity to find (x mod a) + (x mod b) + (x mod c) …?

  c++, math, number-theory

Given an integer x an array of n elements [a1,a2,a3 ... an] (both of which will be taken from input stream) , we wish to find out (x % a1) + (x % a2) + (x % a3) ... + (x % an). x will be given after the taking array as the input.

Since this is part of a bigger problem, I want to find it out preferably in O(1) time (excluding O(n) time for taking in the array).

When I will take the input array, I will simultaneously calculate the sum of the complete array, and wish to bring it into a format similar to (x % (a1 + a2 + a3 ... an)). Is there any identity similar to this?

This is not my actual problem. I just wish to meet my time complexity requirements. Once the array is taken as input, after that, multiple numbers will be given … and I have to calculate the answer for each of them in O(1) time.

Source: Windows Questions C++

LEAVE A COMMENT