# Sum of A[i] % A[j] for all valid i,j

If someone’s interested, you can even solve the question for constraints like n<=10^6 and A[i]<=10^6. But it might need data structures at disposal.

1 Like
Spoiler

I think its possible in O(1e6*log(1e6)) using sieve. No need of fancy data structure. Prefix sum should be sufficient.

Similar problem Problem - B - Codeforces .
Its editorial mentions what we need for solving it for n<=1e6 and A[i]<=1e6.

1 Like

Ya thats right … I was thinking a fenwick tree instead of simple prefix sum (I don’t know why ). I saw this problem and forgot the source. thanks for mentioning it.

1 Like

Have you been able to solve the 1st one ? Others were pretty easy. It would be nice if you share your approach for the 1st one

I also try using prefix sum approach but I failed to implement .

@aryanc403 knows every links.
He is mini Google

Ha vo to hai…Bhai ko kuch bhi puchlo sab Kuch milega😊

1 Like

yes I’m able to solve this…I solve 4/5…just not do 2nd one because I think the question explanation was wrong…

for(int i = 0; i < A.size(); i++)
cnt[A[i]]++;

    for(int i = 1; i <= 1000; i++){
for(int j = 1; j <= 1000; j++){
ans = ans + cnt[i]*cnt[j]*(i%j);
ans = ans%mod;
}
}


No No, not this one. Even I was able to solve this one. But have you been able to solve that sequence problem where you will be given 4 integers a,b,c,d and the sequemce will be an infinite sequence, you are supposed to find the dth term of the sequence. The sequence will contain natural no.s divisible by atleast a,b or c

yes I’m able to solve that also

Oh great. It would be nice if you share how you did that? By the way, then which one you havent

the 2nd one no of unique quadruple

it was simple take a set and put Ax1,Ax2,Ax3,Ax4…AxD
then similarly for B&C…
at last take a counter and output the Dth element in the set

from constraint 2 , it can be said some numbers are duplicates, as size of array is 10^5 but elements are 1<=ele <= 10^3
so to avoid same calculations again and again use HashMap or frequency array, count the frequency of each A[i] and A[j], multiply it and taking mod of elements.

ex :
count 1 = 3 (1,1,1)
count 2 = 4 (2,2,2)
so total 3*4 = 12 pairs of (1,2) will be there but we can count all of their’s contribution by muliplying their frequency at once, which will reduce the time complexity.

below is my java solution.

 public class Solution {
public int solve(int[] A) {

int mod = 1000*1000*1000+7;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0 ; i < A.length ; i++)
map.put(A[i],map.getOrDefault(A[i],0)+1);

long sum = 0;
for(int i = 1 ; i <= 1000; i++){
for(int j = 1; j <= 1000 ; j++){
int freA_i = map.getOrDefault(i,0);
int freA_j = map.getOrDefault(j,0);
sum +=  (freA_i * freA_j)*(i%j);
sum = (sum%mod+mod)%mod;
}
}
return (int)(sum%mod);
}


}