传送门：

花了一些时间理解AC的代码，震惊，代码真的是短小精悍，推理能力很强亦或者是做题多，见的多。

能够理解里面的逻辑真的挺难的

题意

给定n,m，\(1\le x\le m\),求\(\sum_{i=1}^n{( ⌊\frac {a_i} {x} ⌋ +⌊ \frac {x} {a_i} ⌋ )}\)

分析

介绍一下用到的变量。

初始时

a数组存放值cnt[i]表示i出现的次数bkt[i]储存结果

求和分为两部分，分开求解。

part1: \(\sum_{i=1}^n{( ⌊\frac {a_i} {x} ⌋ )}\)

首先预处理cnt数组，处理后 cnt[i] 表示a数组中 >= i的数字有多少个。

然后求他们的后缀和（很神奇！）

part2: \(\sum_{i=1}^n{( ⌊\frac {x} {a_i} ⌋ )}\)

bkt[i+1]储存i能够整除元素（a数组）的数量

i	bkt[i]	储存的值
1	2	1 1
2	3	1 1 2
3	4	1 1 3 3
4	3	1 1 2
5	5	1 1 5 5 5
6	5	11 2 3 3
7	2	1 1

求前缀和，具体为什么可以这样做（我也不知道啊，但是带进去算确实是对的）

Online AC Code

/*参考：https://www.nowcoder.com/acm/contest/view-submission?submissionId=36414030镇海中学 __asm寥寥数行，其中蕴含了很强的推理知识，对前缀、数字有很好的掌握佩服佩服，高中生牛逼*/#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define MAXN 5000010typedef long long lnt;int n, m;lnt bkt[MAXN], cnt[MAXN], ans;int main(){    scanf("%d%d", &n, &m);    // cnt x的出现次数    for (int i = 1, x; i <= n; i++) scanf("%d", &x), cnt[x]++;        cout<<"cnt: "<
         
          = i的数字有多少个。 for (int i = m; i; i--) cnt[i] += cnt[i + 1]; cout<<"cnt: "<