请教杭电ACM第1995题目思路 http://acm.hdu.edu.cn/showproblem.php?pid=1995
2个回答
展开全部
1.拆分成两个不同的素数
2.遇0结束,不是一定要>0,故while(cin>>n && n)
3.你的思路是对的,但这种思路应该会超时,AC不了的
做题时请看清题目...
下面给你偶的代码,用的是Hash算法:
#include<iostream>
using namespace std;
#define N 10002
int prm[N],hash[N];
int i,j;
void prime()
{
for(i=1;i<=N;i++)
hash[i]=1;
hash[1]=0;
for(i=2;i<=N;i++)
{
if(hash[i]==1)
{
j=i+i;
while(j<=N)
{
hash[j]=0;
j+=i;
}
}
}
j=1;
for(i=2;i<=N;i++)
if(hash[i]==1)
{
prm[j++]=i;
}
}
int main()
{
int n,t;
prime();
while(cin>>n,n)
{
t=0;
for(i=1;prm[i]<=n/2;i++)
{
if(hash[n-prm[i]]==1)
t++;
}
if(n%2==0 && hash[n/2]==1)
t--;
cout<<t<<endl;
}
return 0;
}
2.遇0结束,不是一定要>0,故while(cin>>n && n)
3.你的思路是对的,但这种思路应该会超时,AC不了的
做题时请看清题目...
下面给你偶的代码,用的是Hash算法:
#include<iostream>
using namespace std;
#define N 10002
int prm[N],hash[N];
int i,j;
void prime()
{
for(i=1;i<=N;i++)
hash[i]=1;
hash[1]=0;
for(i=2;i<=N;i++)
{
if(hash[i]==1)
{
j=i+i;
while(j<=N)
{
hash[j]=0;
j+=i;
}
}
}
j=1;
for(i=2;i<=N;i++)
if(hash[i]==1)
{
prm[j++]=i;
}
}
int main()
{
int n,t;
prime();
while(cin>>n,n)
{
t=0;
for(i=1;prm[i]<=n/2;i++)
{
if(hash[n-prm[i]]==1)
t++;
}
if(n%2==0 && hash[n/2]==1)
t--;
cout<<t<<endl;
}
return 0;
}
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
2^60直接用long long就行了
#include<cstdio>
int main()
{
int T;
__int64 res[61];
res[0]=1;
for(int i=1;i<61;i++)
res[i]=2*res[i-1];
scanf("%d",&T);
while(T--){
int a,b;
scanf("%d%d",&a,&b);
printf("%I64d\n",res[a-b]);
}
}
#include<cstdio>
int main()
{
int T;
__int64 res[61];
res[0]=1;
for(int i=1;i<61;i++)
res[i]=2*res[i-1];
scanf("%d",&T);
while(T--){
int a,b;
scanf("%d%d",&a,&b);
printf("%I64d\n",res[a-b]);
}
}
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询