2013 acm 长沙网络赛 G题素数+枚举 Goldbach

题目 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3856

先预处理求出两个素数的和与积，然后枚举n-prime和n/prime的情况。

表达式可能的情况 a a*b a+b a+b+c a*b*c a*b+c (注意没有(a+b)*c的情况)

对于a*b和a+b的判重只需要控制 a<=b的范围即可

对于a*b+c的情况不存在重复情况

对于a+b+c a*b*c

分三种情况

①a!=b && b!=c 这种情况对于全枚举会出现三次分别是a+b+c a+c+b b+c+a

②a==b && b!=c 这种情况对于全枚举会出现二次分别是a+b+c a+c+b

③a==b && b==c 这种情况对于全枚举会出现一次分别是a+b+c

为了能够去重可以考虑将②③情况补全成三次然后sum除了3即可

除以3的求模需要注意不能直接mod，需要模3*mod

130ms 代码，8s的时限太给力了。。

  1 #include <stdio.h>
  2 #include<math.h>
  3 #include<string.h>
  4 #define bigt long long
  5 #define N 80005
  6 const int M=80001;
  7 int a[N],p[N];
  8 int pp[N]={0};
  9 int pp2[N]={0};
 10 int pnum;                       
 11 bigt sum =0;                  
 12 bigt sum1 =0;                 
 13 bigt sum2 = 0;                 
 14 const bigt mod = 3000000021LL;
 15 const int mod2 = 1000000007;  
 16 void Prime() {
 17     int i, j;
 18     memset(a, 0, N*sizeof(a[0]));
 19     pnum = 0;
 20     for(i = 2; i < N; ++i) {
 21         if(!a[i]) a[i] = p[pnum++] = i;
 22         for(j = 0; j < pnum && i * p[j] < N; ++j) {
 23             a[i*p[j]] = p[j];
 24             if(!(i%p[j])) break;
 25         }
 26     } 
 27 }
 28        
 29 void init()                   
 30 {
 31     int i=0,j;
 32     do{
 33         for(j=i;j<pnum;j++)
 34         {
 35             if(p[i]+p[j]>M)
 36                 break;
 37             else 
 38             {
 39                 pp[p[i]+p[j]] ++;
 40             }
 41         }
 42         if(p[i]<=sqrt(M*1.0)) 
 43             for(j=i;j<pnum;j++)
 44             {
 45                 if(p[i]*p[j]>M)
 46                     break;
 47                 else 
 48                 {
 49                     pp2[p[i]*p[j]] ++;
 50                 }
 51             }
 52         i++;
 53     }while(i<pnum);
 54 }
 55 
 56 int main()
 57 {
 58     int n;
 59     Prime();
 60     init();
 61     while(scanf("%d",&n)!=EOF)
 62     {
 63         sum = sum1 = sum2  = 0;
 64         if(a[n]==n) sum2++;
 65         
 66         for(int i=0;p[i]<n;i++)
 67         {
 68             int st = p[i];
 69             int ed = n - p[i];
 70             if(ed%2==0 && a[ed/2]==ed/2)
 71             {
 72                 sum1++;
 73                 if(ed/2==st)
 74                     sum1++;
 75             }
 76             
 77             sum1 = sum1 + pp[ed];
 78             sum2 = sum2 + pp2[ed];
 79             
 80             if(a[ed]==ed && 2*st<=n) sum2++;
 81             if(sum1>mod) sum1 -= mod;
 82             if(sum2>mod2) sum2 -= mod2;
 83         }
 84         
 85         sum = (sum1/3 + sum2 )%mod2;
 86         sum1=sum2=0;
 87         
 88         for(int i=0;p[i]<n-1;i++)
 89         {
 90             if(!(n%p[i]))
 91             {
 92                 int st = p[i];
 93                 int ed = n / p[i];
 94                 double tmp = sqrt(ed)+1e-7;
 95                 int tmp2 = (int)tmp;
 96                 
 97                 if(tmp2*tmp2==ed && a[tmp2]==tmp2)
 98                 {
 99                     sum1++;
100                     if(tmp2==st)
101                         sum1++;
102                 }
103                 
104                 sum1 = (sum1 + pp2[ed]);
105                 if(a[ed]==ed &&  st*st<=n) 
106                     sum2++;
107                     
108                 if(sum1>mod) 
109                     sum1 -= mod;
110             }
111         }
112         sum = sum + (sum1/3  + sum2 )%mod2;
113         printf("%lld\n",sum%mod2);
114     }
115     return 0;
116 }

2013 acm 长沙网络赛 G题 素数+枚举 Goldbach

推荐阅读

2013 acm 长沙网络赛 G题素数+枚举 Goldbach