2013 장사 인터넷 경기 G Goldbach FFT

제목 연결 먼저 붙 이기:http://acm.zju.edu.cn/changsha/showProblem.do?problemId=28
       문 제 는 n (1 < = n < = 80000) 을 주 고 최대 세 개의 소수 로 +, * 를 통 해 n 이 모두 몇 가지 방법 이 있 는 지 물 어 보 는 것 이다.예 를 들 어 8 = 2 * 2 * 2 = 2 + 2 * 3 = 2 + 3 + 3 = 3 + 5 이기 때문에 모두 4 가지 입 니 다.또한 같은 수의 다른 기호 도 서로 다른 표현 으로 기억 하 세 요. 예 를 들 어 4 = 2 * 2 = 2 + 2, 이것 은 두 가지 다른 표현 입 니 다.
        먼저 체 소수, 그 다음 에 a, a * b, a * b * c, a * b + c 는 모두 폭력 적 으로 구 할 수 있 습 니 다. 그러면 처리 하기 어 려 운 것 은 주로 a + b 와 a + b + c 두 가지 상황 입 니 다. 여 기 는 두 번 째 fft 로 계산 합 니 다. 첫 번 째 는 k = a + b 에서 각각 몇 가지 표현 방법 이 있 는 지 알 아 보 겠 습 니 다. 여기 서 무 거 운 것 을 판단 하고 a + a 를 삭제 하 는 상황 과 다른 상황 / 2 를 주의 하 세 요. 두 번 째 는 k 를 구 하 는 토대 에서l = k + c 는 모두 몇 가지 표시 방법 이 있 는 지 구 합 니 다. 여기 서 a + b + a 의 상황 을 보충 한 후에 a + b + c = = c + a + b 의 상황 을 처리 하고 마지막 으로 a + a + a 의 상황 을 특별히 판단 하 는 것 이 마지막 답 입 니 다.그리고 8000 안에 있 는 소수 가 모두 8000 개 도 안 되 기 때문에 이 문 제 는 직접 폭력 예 처리 도 할 수 있 습 니 다.......................................................

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=80080;
const int mod=1000000007;
bool ok[maxn];
ll prime[maxn];
int cnt=0;

const double PI = acos(-1.0);
struct comp
{
    double r,i;
    comp(double rt=0,double it=0)
    {
        r=rt;
        i=it;
    }
    comp operator +(const comp& b)
    {
        return comp(r+b.r,i+b.i);
    }
    comp operator -(const comp &b)
    {
        return comp(r-b.r,i-b.i);
    }
    comp operator *(const comp &b)
    {
        return comp(r*b.r-i*b.i,r*b.i+i*b.r);
    }
};

void change(comp y[],int len)//     --    
{
    int i,j,k;
    for(i = 1, j = len/2;i < len-1;i++)
    {
        if(i < j)swap(y[i],y[j]);
        k = len/2;
        while( j >= k)
        {
            j -= k;
            k /= 2;
        }
        if(j < k)j += k;
    }
}

void fft(comp y[],int len,int on)
/* on=1 DFT                   ；
on=-1,IDFT                 */
{
    change(y,len);
    for(int h = 2;h <= len;h <<= 1)
    {
        comp wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for(int j = 0;j < len;j += h)
        {
            comp w(1,0);
            for(int k = j;k < j+h/2;k++)
            {
                comp u = y[k];
                comp t = w*y[k+h/2];
                y[k] = u+t;
                y[k+h/2] = u-t;
                w = w*wn;
            }
        }
    }
    if(on == -1)
        for(int i = 0;i < len;i++)
            y[i].r /= len;
}

void conv(comp f[],int len)// f   
{
    fft(f,len,1);
    for (int i=0; i<len; i++)
    f[i]=f[i]*f[i];
    fft(f,len,-1);
}

void ss()
{
    memset(ok,true,sizeof ok);
    ok[2]=true;
    ok[1]=false;
    ok[0]=false;
    for (int i=2; i<maxn; i++)
    {
        if (ok[i])
        {
            for (int j=i+i; j<maxn; j+=i)
            if (ok[j]) ok[j]=false;
        }
    }
    cnt=0;
    for (int i=2; i<maxn; i++)
    if (ok[i])
    {
        prime[cnt++]=i;
    }
//    for (int i=0; i<cnt; i++)
//    cout<<prime[i]<<"
";
//    cout<<endl;
//    cout<<cnt<<endl;
}
ll ans=0;
ll n;
ll tm[maxn<<2],num[maxn<<2],sum[maxn<<2];
comp x[maxn<<2],y[maxn<<2],z[maxn<<2];
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    cnt=0;
    ss();
    memset(tm,0,sizeof tm);
    memset(num,0,sizeof num);
    memset(sum,0,sizeof sum);

    n=80000;
    int len=1;
    while(len<2*n) len<<=1;

    for (int i=0; i<n; i++)
    if (ok[i]) x[i]=comp(1,0);
    else x[i]=comp(0,0);

    for (int i=n+1; i<len; i++)
    x[i]=comp(0,0);

    fft(x,len,1);
    for (int i=0; i<len; i++)
    x[i]=x[i]*x[i];
    fft(x,len,-1);

    for (int i=0; i<len; i++)
    num[i]=(int)(x[i].r+0.5);

    for (int i=0; i<=n; i++)
    if (ok[i]) num[i+i]--;
    for (int i=0; i<=n; i++)
    num[i]/=2;

    for (int i=0; i<=n; i++)
    x[i]=comp(num[i],0);

    for (int i=n+1; i<len; i++)
    x[i]=comp(0,0);

    for (int i=0; i<=n; i++)
    if (ok[i]) y[i]=comp(1,0);
    else y[i]=comp(0,0);
    for (int i=n+1; i<len; i++)
    y[i]=comp(0,0);

    fft(x,len,1);
    fft(y,len,1);
    for (int i=0; i<len; i++)
    x[i]=x[i]*y[i];
    fft(x,len,-1);
    for (int i=0; i<len; i++)
    sum[i]=(int)(x[i].r+0.5);


    while(~scanf("%d",&n))
    {
        ans=0;
        if (ok[n]) ans++;//a

        for (int i=0; i<cnt && prime[i]<=n; i++)
          for (int j=i; j<cnt&& prime[j]<n && prime[i]*prime[j]<=n; j++)
          if (prime[i]*prime[j]==n) ans++;  //a*b


        for (int i=0; i<cnt && prime[i]<=n; i++)
          for (int j=i; j<cnt&& prime[i]*prime[j]<=n; j++)
          {
              int tp=n-prime[i]*prime[j];
              if (ok[tp]) ans++;//a*b+c
          }

        for (int i=0; i<cnt && prime[i]<=n; i++)
          for (int j=i; j<cnt&& prime[i]*prime[j]<=n; j++)
           for (int k=j; k<cnt&& prime[i]*prime[j]*prime[k]<=n; k++)
           if (prime[i]*prime[j]*prime[k]==n) ans++;//a*b*c

        if (n%2==0 && ok[n/2]) ans++;
        ans+=num[n];//a+b

        ans%=mod;
        int tmp=0;
        for (int i=0; i<=n; i++)
        {
            if (ok[i])
            {
                int tp=n-i;
                if (tp%2==0 && ok[tp/2]) tmp++;
            }
        }
        ans=(ans+(sum[n]+2*tmp)/3)%mod;
        if (n%3==0 && ok[n/3]) ans++;
        ans%=mod;
        //a+b+c
        printf("%d
",ans);
    }
    return 0;
}