首页 > ACM题库 > HDU-杭电 > HDU 3463-Goldbach Division[解题报告]HOJ
2014
03-30

HDU 3463-Goldbach Division[解题报告]HOJ

Goldbach Division

问题描述 :

Everybody knows Goldbach Conjecture! Here is one edition of it:

1) Every odd integer greater than 17 can be written as three different odd primes’ sum;
2) Every even integer greater than 6 can be written as two different odd primes’ sum.

Loving the magical math conjecture very much, iSea try to have a closer look on it. Now he has a new definition: Goldbach Division. If we express an even integer as two different odd primes’ sum, or odd integer as three different odd primes’ sum, we call it a form of Goldbach Division of N, using a symbol G(N).

For example, if N = 18, there are two ways to divide N.
18 = 5 + 13 = 7 + 11
If N = 19, there is only one way to divide N.
19 = 3 + 5 + 11

Here comes your task, give a integer N, find |G(N)|, the number of different G(N).

输入:

There are several test cases in the input.

Each test case includes one integer N (1 <= N <= 20000).

The input terminates by end of file marker.

输出:

There are several test cases in the input.

Each test case includes one integer N (1 <= N <= 20000).

The input terminates by end of file marker.

样例输入:

18
19

样例输出:

2
1
Hint
There may be 2000 cases, be careful.

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

int prime[3000],num;
int ans[20010];

void init()
{
 bool succ[20010];
 num=0;
 memset(succ,0,sizeof(succ));
 for (int i=2;i<=20000;i++)
 if (!succ[i])
 {
 prime[num++]=i;
 for (int j=i*i;j<=20000;j+=i)
 succ[j]=true; 
 } 
 memset(ans,0,sizeof(ans));
 for (int i=1;i<num;i++)
 for (int j=i+1;j<num&&(prime[i]+prime[j]<=20000);j++)
 ans[prime[i]+prime[j]]++;
 
 for (int i=6;i<=20000;i+=2)
 for (int j=1;j<num&&(i+prime[j]<20000);j++)
 ans[prime[j]+i]+=ans[i];
 
 for (int i=1;i<num&&(2*prime[i]<20000);i++)
 for (int j=1;j<num&&(2*prime[i]+prime[j]<20000);j++)
 if (j!=i)
 ans[2*prime[i]+prime[j]]--;
 
 for (int i=3;i<=20000;i+=2)
 ans[i]/=3;
}

int main()
{
 init();
 int n;
 while(scanf("%d",&n)!=EOF)
 {
 printf("%d\n",ans[n]); 
 }
 return 0; 
}

  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。