Question

关于北大ACM JudgeOnline的3006题（Dirichlet's Theorem on Arithmetic Progressions）

题在这个网站上：
http://acm.pku.edu.cn/JudgeOnline/problem?id=3006
我所有样数都通过了，为什么还是wrong answer呢？

#include<stdio.h>
int num[1000000]={1,1},prime[1000000];
void main()
{
int i,j=1,k,count=0,n;
int a[100],b[100],c[100];
for(k=0;k<100;k++)
{
scanf("%d %d %d",&a[k],&b[k],&c[k]);
if(a[k]==0&&b[k]==0&&c[k]==0)
break;
}
for(i=2;i<1000;i++)
if(num[i]==0)
for(j=i*2;j<1000000;j+=i)
num[j]=1;
for(i=0,j=0;i<1000000;i++)
if(num[i]!=1)
prime[j++]=i;
for(n=0;n<k;n++)
{
for(i=0;;i++)
if((prime[i]-a[n])>=0)
break;
for(count=0;i<1000000;i++)
if((prime[i]-a[n])%b[n]==0&&prime[i]!=0)
{
count++;
if(count==c[n])
{
printf("%d\n",prime[i]);
break;
}
}
}
}

Answer 1

ACM的体系就是这样,没办法,基本不允许你写任何不规范的代码

比如要求A+B的值,并输出其值

错误代码:
#include<stdio.h>

int main()
{
int a,b;
while(scanf("%d%d",&a,&b))
printf("%d",a+b);
return 0;
}

正确代码:

#include<stdio.h>

int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
printf("%d",a+b);
return 0;
}

你的代码算法可能没有问题,但输入方面肯定有问题,比如他的输入应该是很多测试数据,你只定义100个可能不满足他的要求,甚至10000个都不满足,你应该这样,我只给你写这一点地方,后面的你自己改,输入的数据不要用数组,下面只写输入语句部分:

while(scanf("%d%d%d",&a,&b,&c)!=EOF&&(a||b||c)){...}

前面的A,B,C的定义当然就要改了,后面的调用A,B,C的地方也一样要改,就改成A,B,C就行

我给你改了一下代码,看样子你的算法也要改了,要改得效率更高点.我提交的时候显示超时了

搞定了
3318959 PcrazyC 3006 Accepted 696K 0MS C++ 670B 2008-04-18 09:45:57

#include<iostream>
#include<cmath>

#define N 1000000

using namespace std;
bool A[N]={1};

void prime(int n) //用筛法将不是素数的值置0
{
int i,j;
double k=sqrt((float)n);
for(i=3;i<=k;i+=2) //只要考虑小于 n的开方 就可以了,
{
if(A[i/2]!=1)
for(j=i*i;j<=n;j+=2*i) //i的平方以内的已经被筛选掉了,所以从i的平方开始
A[j/2]=1;
}
}

int main()
{
int a,d,n,i,count;
prime(N);
while(scanf("%d%d%d",&a,&d,&n)!=EOF&&(a||d||n))
{
count=0;
for(i=a;count<n;i+=d)
if(i==2||(i%2==1&&A[i/2]==0))
count++;
printf("%d\n",i-d);
}
return 0;
}

哈哈,我居然第二:
Rank Run ID User Memory Time Language Code Length Submit Time
1 3251154 chhung6 352K 0MS G++ 805B 2008-04-02 23:19:57
2 3318959(5) PcrazyC 696K 0MS C++ 670B 2008-04-18 09:45:57
3 2465761(2) crackerwang 1140K 0MS G++ 432B 2007-08-07 21:27:35
4 3036682(3) R2D2 1272K 0MS G++ 1649B 2008-01-12 12:33:06
5 3129378 j0533st 1348K 0MS G++ 552B 2008-02-28 17:43:50
6 1680562 cheapwine 316K 15MS G++ 2593B 2006-10-18 11:01:59
7 2700011 ACM06Louty 1272K 15MS G++ 603B 2007-09-23 20:57:46
8 3123681(2) laj5122 2048K 15MS Pascal 603B 2008-02-26 15:33:04
9 3318632(3) Julian_tan 1184K 16MS C++ 1160B 2008-04-18 02:34:10
10 2913313 testerforL 1072K 30MS C++ 656B 2007-11-16 15:22:19