CSAPC09 质均数

题目解答

1. 直接找规律，第一个是5，第二个就是下一个质数7，以此类推……
2. 发现关系后用规律去做：关系是任何一个质数(>=5)都可以被两个质数相加除以2得到。(仅为猜想，没有证明)，然后就直接有了一个直接找规律

运行情况

程序清单

#include<iostream>
using namespace std;
long n,num[4],maxn,num1[451];
bool prime[1000001];//肯定有猛人交一个450字元的表, 其实构造素数也不会超时 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) {cin>>num[i];if(num[i]>maxn) maxn=num[i];}
    int k=0;
    for(long i=2;i<=50000;i++)//我就懒得优化了 ,直接枚举!!!
    {
      if(!prime[i])
      for(long j=2;j<=100000;j++)
      if(j*i<=1000000)
        prime[j*i]=true;
      else break;
    }
    for(long i=5;i<=1000000;i++)
    if(!prime[i])
    {
      k++;
      if(k<=maxn)
        num1[k]=i;
      else break;
    }
    for(int i=1;i<=n;i++)
      cout<<num1[num[i]]<<endl;
    return 0;
}

注意事项

如果我没有看错ZeroJudge给的难度是3，其实应该改为1.因为我大概迟到了一个小时考试，再加上一试考的不好，所以就做了这道(当时一看就知道这题好做)，然后就离场了。另外我比较感兴趣的是第3题，有时间写个题解

难易等级

So Easy(Noip the 1st)