ZOJ Goldbach 2013年长沙赛区网络赛
迟到了一天的AC。。。。
思路：
先把单个素数 或着 两个素数能组成的情况预处理一下，然后对于给出的 n，拿第三个素数去和两个素数的情况匹配，最后要注意去重。
详情见代码。
因为手残少敲了一个 else ，Debug了一晚上。。。
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>using namespace std;const long long int INF = 1000000007;bool MarkVisit[80010] = {false};long long int pri[80010];long long int s[80010] = {0};long long int sm[80010] = {0};//a*along long int sa[80010] = {0};//a+along long int dm[80010] = {0};//a*blong long int da[80010] = {0};//a+bint main(){ int i,j; int top = 0; for(i = 2; i <= 80000; ++i)//挫到荼靡的素数筛。。。 { if(MarkVisit[i] == false) { pri[top++] = i; for(j = i+i; j <= 80000; j += i) { MarkVisit[j] = true; } } } for(i = 0; i < top; ++i)//预处理 { s[pri[i]]++;//一个素数的情况 if(pri[i]*2 <= 80000) { sa[pri[i]*2]++;//两个相同的素数相加的情况 } if(pri[i]*pri[i] <= 80000) { sm[pri[i]*pri[i]]++;//两个相同的素数相乘的情况 } for(j = i+1; j < top; ++j) { if(pri[i] + pri[j] <= 80000) { da[pri[i] + pri[j]]++;两个不相同的素数相加的情况 } if(pri[i]*pri[j] <= 80000) { dm[pri[i]*pri[j]]++;//两个不相同的素数相乘的情况 } } } int n; long long int tempsum, sum; while(scanf("%d",&n) != EOF) { sum = s[n] + dm[n] + da[n] + sa[n] + sm[n];//先把一个或两个素数的情况统计出来 for(i = 0,tempsum = 0; i < top; ++i) { if(n%pri[i] == 0) { if(n == pri[i]*pri[i]*pri[i])//如果三个数相同 则此种情况重复计算一次 *3 补成三次 { tempsum += sm[n/pri[i]]*3 + dm[n/pri[i]]; } else tempsum += sm[n/pri[i]]*2 + dm[n/pri[i]];//如果只有来两个相同 则此种情况重复计算两次。 //因为另一种单独计算 所以只需对其中一次*2 补成三次 } if(n >= pri[i]) { sum += sm[n-pri[i]];//+ && *都出现的不会重复 sum += dm[n-pri[i]]; sum %= INF; if(n == pri[i]*3)//此种情况 和 * 形同 不再赘述 { tempsum += da[n-pri[i]] + sa[n-pri[i]]*3; } else tempsum += da[n-pri[i]] + sa[n-pri[i]]*2; //就是因为少了这个else...险些把这一晚上都废了。。。 } else break; } sum %= INF; sum += tempsum/3;//因为每一种都出现了3次 sum %= INF; printf("%lld\n",sum); } return 0;}