比赛的时候，被题目误导了，题目最后说结果可能很大，要取模，那时就想直接求会TLE的！！！
赛后才知道，坑啊…………
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define M 80001
#define mod 1000000007
using namespace std;
int prime[M/],cnt,p[M];
bool f[M];
void init()
{
cnt=;
memset(f,,sizeof(f));
for(int i=;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
memset(p,-,sizeof(p));
}
int cal(int n)
{
int nn=n;
if(p[n]!=-) return p[n];
int m=;
for(int i=;i<cnt&&prime[i]<=nn;i++){
if(nn%prime[i]==){
m++;
nn/=prime[i];
while(nn%prime[i]==){
m++;
if(m>) return p[n]=;
nn/=prime[i];
}
if(m>) return p[n]=;
}
}
if(nn>) m++;
if(m>) return p[n]=;
return p[n]=m;
}
int main()
{
int n;
init();
while(scanf("%d",&n)!=EOF){
int ans=;
if(!f[n]||cal(n)<=) ans++;//全是乘法
for(int i=;i<cnt&&prime[i]<=n;i++){//乘法和加法
if(cal(n-prime[i])==) ans++;
}
for(int i=;i<cnt&&*prime[i]<=n;i++)//2个数加
if(f[n-prime[i]]==) ans++;
for(int i=;i<cnt&&*prime[i]<=n;i++){//三个数加
for(int j=i;prime[i]+*prime[j]<=n;j++)
if(f[n-prime[i]-prime[j]]==) ans++;
}
printf("%d\n",ans);
}
return ;
}