传送门：算式子

花了一些时间理解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数组）的数量

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

Online AC Code

/*参考：/acm/contest/view-submission?submissionId=36414030镇海中学 __asm寥寥数行，其中蕴含了很强的推理知识，对前缀、数字有很好的掌握佩服佩服，高中生牛逼*/#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>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: "<<endl;for(int i=1;i<=m;i++) cout<<cnt[i]<<" "; cout<<endl;// 储存第二部分的结果？？for (int i = 1; i <= m; i++)for (int j = i; j <= m; j += i) bkt[j] += cnt[i];for(int i=1;i<=m;i++)cout<<bkt[i]<<" ";cout<<endl;// 前缀和？for (int i = 1; i <= m; i++) bkt[i] += bkt[i - 1];for(int i=1;i<=m;i++) cout<<bkt[i]<<" "; cout<<endl;// 预处理第一部分？// 处理后 cnt[i] 表示>= i的数字有多少个。for (int i = m; i; i--) cnt[i] += cnt[i + 1];cout<<"cnt: "<<endl;for(int i=1;i<=m;i++) cout<<cnt[i]<<" "; cout<<endl;// 计算第一部分的结果？for (int i = 1; i <= m; i++)for (int j = i; j <= m; j += i)bkt[i] += cnt[j];for(int i=1;i<=m;i++) cout<<bkt[i]<<" "; cout<<endl;// 计算结果？for (int i = 1; i <= m; i++)ans ^= bkt[i]; printf("%lld\n", ans);return 0;}

如果觉得《【牛客网】牛客练习赛19 F 算式子【数学--递推 前缀 数字】》对你有帮助，请点赞、收藏，并留下你的观点哦！