力扣1862.向下取整数对和

力扣1862.向下取整数对和

• 前缀和 + 公式推导

  • 对于floor函数，**[0,i-1] [i,i×2-1] [i×2,i×3-1] [i×3,i×4-1] …[i×(j-1),i×j-1]**的区间内floor值相同
  • 对于每个元素i，每次找区间内元素个数y，以及元素i的个数x
  • 得到res += y * x * (j / i)

•   class Solution {const int N = 1e9+7;long num[100010];public:int sumOfFlooredPairs(vector<int>& nums) {long long res = 0;int n = nums.size(),maxx=0;//找最大值(上限)for(int i=0;i<n;i++)maxx = max(maxx,nums[i]);//记录每个元素出现次数(元素最大值10w,较小)for(int i=0;i<n;i++)num[nums[i]] ++;//求前缀和for(int i=1;i<=maxx;i++)num[i] += num[i-1];for(int i=1;i<=maxx;i++){//元素i的个数xlong x = num[i] - num[i-1];if(x == 0) continue;//遍历倍数j,每次+=i,跳到下一个区间for(int j=i;j<=maxx;j+=i){//这个区间的元素个数ylong y = num[min(j+i-1,maxx)] - num[j-1];res = (res + (j/i)*y*x)%N;}}return (int)res;}};