2017 搜狗校园招聘 距离的总和
题目描述：
时间限制：c/c++ 2000MS
定义两个大于2的偶数之间的距离，为这两个数之间质数的个数。从小到大输入n个大于2的偶数，输出所有数两两之间距离的总和（应该有n*(n-1)/2个距离，输出总和就好)。
输入
第一行是输入偶数的个数，最小为2，最大可能到几万。之后每行为一个偶数，最小是4，最大可能是几百万，不重复的升序排列。
输出
输入数据两两间距离的总和，这应该是一个不小于0的整数。
样例输入
3
4
6
12
样例输出
6
输入
第一行是输入偶数的个数，最小为2，最大可能到几万。之后每行为一个偶数，最小是4，最大可能是几百万，不重复的升序排列。
输出
输入数据两两间距离的总和，这应该是一个不小于0的整数。
样例输入
3
4
6
12
样例输出
6
看到题目我的想法是预处理算出一个数前面有多少个质数，然后利用区间减法的性质，可以得到任意区间的质数的个数。然后就是数每一个小区出现的次数，不难得到，这个次数为（n - i）*i,然后从左到右扫描累加和即可。当时我没有做出来。内存超限。
Read full article from 距离的总和 - y119777 - 博客园
No comments:
Post a Comment