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 https://codeforces.com/contest/850/problem/B .
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 .

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