数学カウント-2013 ACM/ICPC Asia Regional Changsha Online-Gタイトル

テーマリンク:
http://acm.zju.edu.cn/changsha/showProblem.do?problemCode=G
タイトルの大意:
一つの数x（1<=x==80000）をあげて、2種類の運算で足し算と掛け算をすることができて、最大3つの素数を使って聞いて、xに集まって全部でどれだけの方法がありますか？
問題解決の考え方：
数学の数
素数フィルタを使って素数を絞り出します。全部で8000個しかないので、o(n^2)を使ってもいいです。
それから状況によって討論します。
1、掛け算だけで、一つの素数が掛け合われ、二つの素数が掛け合われ、三つの素数が掛け合われます。注意は素数を掛け合わせることです。
2、かけ算があります。一つの素数を差し引き、二つの素数を掛け合わせることができるかどうかを判断します。
3、3つの素数の加算。三つの場合に分けて、待ちたくないです。同じ二つがあります。三つとも同じです。
4、2つの素数の加算。二つの場合に分けて、等しくない、等しい。
先に前処理して、二つの異なる素数からなるのとiの種数で、同じ種数です。
コードの説明はとても詳しいです。
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 81000

bool prime[Maxn];
int pp[8000],cnt; //       7378 
int num1[200000],num2[200000]; //num1[i]    i            
//num2[i]    i             
void init()
{
    memset(prime,true,sizeof(prime));
    prime[0]=0;
    prime[1]=0;
    int n=80000;
    for(int i=2;i<=sqrt(n*1.0);i++)
    {
        if(prime[i])
        {
            for(int j=i*2;j<=n;j+=i)
                prime[j]=0;
        }
    }
    cnt=0;
    for(int i=2;i<=n;i++)
        if(prime[i])
            pp[++cnt]=i;
    for(int i=1;i<=cnt;i++) //o(8000^2) 8s    
        for(int j=i+1;j<=cnt;j++)
            num1[pp[i]+pp[j]]++;
    for(int i=1;i<=cnt;i++)
        num2[pp[i]+pp[i]]++;
    //printf("%d
",cnt);
}
int mul(int n,int num)//  num          n
{
    if(prime[n]) //
    {
        if(num==1)
            return 1;
        else
            return 0;
    }
    int res=0;
    for(int i=1;pp[i]*pp[i]<=n&&i<=cnt;i++)
    {
        while(n%pp[i]==0)
        {
            n/=pp[i];
            res++;
            if(res>num)
                return 0;
        }
    }
    if(n!=1)
        res++;
    if(res==num)
        return 1;
    return 0;

}

int main()
{
   init();
   int x;
   ll ans;

   while(~scanf("%d",&x))
   {
       ans=0;
       ans+=mul(x,1); //      
       ans+=mul(x,2); //      
       ans+=mul(x,3); //      

       //         
       for(int i=1;i<=cnt;i++)
       {
           int t=x-pp[i];
           if(t<4)
                break;
           ans+=mul(t,2);
       }
       //      
       //       
       ll temp=0;
       for(int i=1;i<=cnt;i++)
       {
           int t=x-pp[i]; //     

           if(t>=2)
           {
               if(t-pp[i]>=2&&prime[t-pp[i]])
               {
                   if(x==pp[i]*3) //     pp[i]     
                        temp+=num1[t];
                   else
                       temp+=num1[t]-1; //     pp[i]       

               }
               else
                    temp+=num1[t];
           }
           else
                break;
       }
       ans+=temp/3; //            
       //     ,       
       for(int i=1;i<=cnt;i++)
       {
           int t=x-pp[i]*2;
           if(t>=2)
           {
               if(prime[t])
               {
                   if(t!=pp[i])
                        ans++;
               }
           }
           else
                break;
       }
       //    
       for(int i=1;i<=cnt;i++)
       {
           if(x>=pp[i]*3)
           {
               if(x==pp[i]*3)
                    ans++;
           }
           else
                break;
       }
       //     
       //        
       ans+=num1[x];
       //     
       ans+=num2[x];
       printf("%lld
",ans);

   }
   return 0;
}