Prefix sum of frequency counts
\n#define ll long long int\nconst int mod=1e9+7;\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& a) {\n        ll i,n=a.size(),j,mx=-1;\n    
```\n#define ll long long int\nconst int mod=1e9+7;\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& a) {\n        ll i,n=a.size(),j,mx=-1;\n        \n        for(i=0;i<n;i++)\n            if(mx<a[i])\n                mx=a[i];\n        \n        bool vis[mx+10];\n        memset(vis,0,sizeof(vis));\n        \n        ll mxx=mx<<2;\n         \n        ll f[10+mxx],pf[10+mxx];\n        memset(f,0,sizeof(f));\n        \n        for(i=0;i<n;i++)\n            f[a[i]]++;\n        \n        pf[0]=f[0];\n        for(i=1;i<10+mxx;i++)\n            pf[i]=pf[i-1]+f[i];\n        \n        ll ans=0;\n        \n        for(j=0;j<n;j++){\n            i=a[j];\n            if(vis[i])\n                continue;\n            \n            vis[i]=1;\n            ll left=i-1,right=2*i-1,mf=1;\n            ll cntl=pf[left],cntr=pf[right];\n            \n            while(left<=mx){\n                ans=(ans+(mf*(f[i]*(cntr-cntl))%mod)%mod)%mod;\n                \n                left+=i;\n                right+=i;\n                \n                cntl=pf[left];\n                cntr=pf[right];\n                \n                mf++;\n            }\n        }\n        \n        return ans;\n    }\n};\n```
['C', 'Prefix Sum', 'C++']