Baudelaire is Programmer

我们将所有能写成 p²+q² (p,q>=0)的数字成为bisquare数，在bisquare集合中有多少长度为N(3<=N<=25)的等差序列？我们规定p,q的取值区间为[0,M](1<=M<=250)，且等差序列的公差大于0。

我们很容易想到枚举序列中的前两项（或者首项和尾项，这正是我用的方法，这样便于剪枝）来确定整个序列并检验其余项是否是bisquare，但注意当M=250的时候bisquare集合中有20000多个数字，所以算法的复杂度要控制在o(n²)以内，这样检验是否是bisquare的步骤要用常数时间才行，这时候哈希表就派上用场了。

点击查看我的源代码：

/*
ID: *******
LANG: C
TASK: ariprog
*/
#include<stdio.h>
#include<stdlib.h>

int N,M;
FILE *fin,*fout;
typedef struct{
    int first;
    int diff;
}R;
R seq[10001];
int tailSeq;
int bisq[32000];
int tailBisq;
int hash[125001];

int cmpint(const void *a, const void *b){
	return(*(int *)a-*(int *)b); //升序 
}

int cmpR(const void *a, const void *b){//先按公差比较，再按首项比较 
	R aa=*(R*)a;
	R bb=*(R*)b;
	if(aa.diff==bb.diff){
		return aa.first-bb.first;
	}
	return aa.diff-bb.diff;
}

int main(){
    fin=fopen("ariprog.in","r");
    fout=fopen("ariprog.out","w");
    fscanf(fin,"%d %d",&N,&M);
    int i,j;
    for(i=0;i<125001;i++)hash[i]=0;
    tailBisq=-1;
    for(i=0;i<=M;i++){
		for(j=i;j<=M;j++){
			bisq[++tailBisq]=i*i+j*j;
			hash[bisq[tailBisq]]=1;//哈希表记录某数字是否在bisquare数字集合中 
		}
    }
    qsort(bisq,tailBisq+1,sizeof(int),cmpint);
    int count=0;
    int pre=-1;
    for(i=0;i<=tailBisq;i++){//排序后去重 
		if(bisq[i]!=pre){
			bisq[count]=bisq[i];
			count++;
			pre=bisq[i];
		}
	}
	tailBisq=count-1;

    tailSeq=-1;
    int first,last;
    for(first=0;first<=tailBisq;first++){
		for(last=first+N-1;last<=tailBisq;last++){//枚举首项和尾项 
			int diff=bisq[last]-bisq[first];
			if(diff==0)continue;
			if(diff%(N-1)!=0)continue;//剪枝
			diff=diff/(N-1);
			for(i=1;i<=N-2;i++)//查看中间项是否是bisquare数 
				if(hash[bisq[first]+diff*i]==0)
					break;
			if(i>N-2){//记录符合条件的等差序列 
				R r;
				r.first=bisq[first];
				r.diff=diff;
				seq[++tailSeq]=r;
			}
		}
	}
	qsort(seq,tailSeq+1,sizeof(R),cmpR);
	for(i=0;i<=tailSeq;i++){
		fprintf(fout,"%d %d\n",seq[i].first,seq[i].diff);
	}
	if(tailSeq==-1)fprintf(fout,"NONE\n");
    return 0;
}