距离的总和

63 阅读 0 评论 42 点赞

我是靠谱客的博主优美过客，最近开发中收集的这篇文章主要介绍距离的总和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2017 搜狗校园招聘距离的总和

题目描述：

时间限制：c/c++ 2000MS

定义两个大于2的偶数之间的距离，为这两个数之间质数的个数。从小到大输入n个大于2的偶数，输出所有数两两之间距离的总和（应该有n*(n-1)/2个距离，输出总和就好)。
输入
第一行是输入偶数的个数，最小为2，最大可能到几万。之后每行为一个偶数，最小是4，最大可能是几百万，不重复的升序排列。
输出
输入数据两两间距离的总和，这应该是一个不小于0的整数。

样例输入
3
4
6
12
样例输出
6

看到题目我的想法是预处理算出一个数前面有多少个质数，然后利用区间减法的性质，可以得到任意区间的质数的个数。然后就是数每一个小区出现的次数，不难得到，这个次数为（n - i）*i,然后从左到右扫描累加和即可。当时我没有做出来。内存超限。

 1 #include<bits/stdc++.h>
 2 #define pb push_back
 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
 5 typedef long long ll;
 6 using namespace std;
 7 typedef pair<int, int> pii;
 8 const int maxn = 1e3 + 10;
 9 void solve() {
10     int n;
11     scanf("%d", &n);
12     vector<int> a(n);
13     unordered_map<int, int> m;
14     int x, ma = 1;
15     for (int i = 0; i < n; i++) {
16         scanf("%d", &x); m[x]++; ma = max(ma, x);
17         //cout <<x << endl;
18     }
19     vector<bool> p(ma + 1, 0);
20     vector<int> b;
21     int cnt = 0;
22     for (int i = 2; i <= ma; i++) {
23         if(m.count(i)) {
24             for (x = 0; x < m[i]; x ++) b.pb(cnt);
25         }
26         if(p[i]) continue;
27         cnt ++;
28         for (ll j = 1ll * i * i; j <= ma; j += i) {
29             p[j] = 1;
30         }
31     }
32     ll res = 0;
33     for (int i = 0; i < n - 1; i++) {
34         res += (b[i + 1] - b[i]) * (n - i - 1) * (i + 1);
35     }
36     printf("%I64dn", res);
37 }
38 int main() {
39     freopen("test.in", "r", stdin);
40     //freopen("test.out", "w", stdout);
41     solve();
42     return 0;
43 }