Reverse Logic Count Prefix Sum with Sieve method O(nlogn) Complexity
Intuition\n Describe your first thoughts on how to solve this problem. \n- Here we are going to think in reverse order\n- we are going to fix denominator and fl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Here we are going to think in reverse order\n- we are going to fix denominator and floor fractional result and we are going to find how many numerators satisfy this condition.\n- we need **prefix count sum(sieve method)**\n\n***Main Intuition***\n- for ex: **[2,5,9]** we if we fix **2** as denominator and we calculate prefix count sum which is **[1->0,2->1,3->1,4->1,5->2,6->2,7->2,8->2,9->3..]**\n- for ranges if we fix as numerator \n[0,1] res = 0\n[2,3] res = 1\n[3,4] res = 2\n...\nas we can observe that if we iterate for res i.e 0,1,2.. till 1e5 then we can go on fixing ranges\n- **formula for ranges result as j = [j * denominator,j * (denominator+1)-1]** for this interval the res = j so we just need count in this range which can be obtained by **count prefix sum**\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int MOD = 1e9+7;\n    long long N = 100000;\n    int sumOfFlooredPairs(vector<int>& nums) {\n        vector<long long> count(N+1,0);\n        //This is the count Prefic sum(Method is Sieve Method)\n        unordered_set<long long> se;\n        //initially store all the counts in vector count also store in set\n        for(auto &x : nums) {\n            count[x]++;\n            se.insert(x);\n        }\n\n        //now Get the prefix sum of all the count\n        //we are doing this becoz we need count in between range [left,right] \n        //for that we are doing this\n        for(int i=1;i<=N;i++) {\n            count[i] += count[i-1];\n        }\n\n        //we need to fix denominator and check for each number \n        //this is reverse thinking we are getting numerator for given ans of fraction\n        long long ans = 0;\n        for(auto &i : se) {\n            //i is denominator\n            long long val = 0;\n            for(int j = 1; i*j <= N; j++) {\n                //j denotes the floor fraction result\n                //for range [left,right] = [i*j, i*(j+1)-1] we get j as fractional result try it \n                long long left = i*j;\n                long long right = i*(j+1) - 1;\n                right = min(right,N); // for not exceeding 1e5\n                long long cnt = count[right] - count[left-1]; //getting number of elements in this range \n                //why? becoz for that many elements if we fix them as numerator we are gonna get "j" as floor fractional result\n\n                //after that store all the results sum in val which means for that particular denominator this is result\n                val = (val + (cnt*j) % MOD) % MOD;\n            }\n            //there might be more than 1 frequency if denominator\n            //we can get by count[i] - count[i-1] which gives frequency of i\n            long long c = count[i] - count[i-1];\n            //multiply and store the result\n            ans = (ans + (val*c) % MOD) % MOD;\n        }\n        return ans;\n    }\n};\n```
['C++']