C++ implementation | SOE and Prefix SUM
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. calculate sieve arra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. calculate sieve array\n2. calculate prefix sum of sieve array\n3. iterate a loop to find the value and update the sum value.\n\n# Complexity\n- Time complexity:\n- O(N logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#define ll long long int\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& nums) {\n         ll mx = 1e5;\n         vector<ll>sieve(mx+2,0),prefix(mx+2,0);\n         for(auto i :  nums)\n            sieve[i]++;\n        for(ll i=1;i<=mx;i++){\n            prefix[i] = prefix[i-1]+sieve[i];\n        }\n        ll ans = 0;\n        ll mod = 1e9+7;\n        for(ll i=1;i<=mx;i++){\n            ll count =1;\n            for(ll j=i;j<=mx;j+=i){\n                ll start = j;\n                ll end = j+i-1;\n                end = min(mx,end);\n                ll sum  = ((prefix[end]-prefix[start-1])*count)%mod;\n                sum = (sum*sieve[i])%mod;\n                ans+=sum;\n                ans%=mod;\n                count++;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']