pku1840.txt

PKU 1840的代码！ 有详细的解题目报告！

//pku1840
#include<stdio.h>
#include<string.h>
#define M 55457//prime
int pow[101];
struct me
{
 __int64  val;
 __int64  num;
 
}a[M];
int main()
{
   int i,j,k,a1,a2,a3,a4,a5;
   __int64 p,value,sum,sum0,ans;
   j=0;
   for(i=-50;i<=50;i++)
   {
	   pow[j]=i*i*i;
	   j++;
   }
   while(scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)!=EOF)
   {
      memset(a,0,sizeof(a));
      for(i=-50;i<=50;i++)
	  {
         if(i==0)
			 continue;
          for(j=-50;j<=50;j++)
		  {
            if(j==0)
				continue;
             value=-a1*pow[i+50]-a2*pow[j+50];
             p=(__int64)(value*value)%M;
             while(a[p].num&&a[p].val!=value)
				 p=(p+1)%M;
             if(a[p].num==0)
			 {
                a[p].val=value;
                a[p].num++;
			 }
           else 
			   a[p].num++;
    
		  }
	  }
     ans=0;
     for(i=-50;i<=50;i++)
	 {
        if(i==0)
			continue;
        sum0=a3*pow[i+50];
        for(j=-50;j<=50;j++)
		{
            if(j==0)
				continue;
           sum=sum0+a4*pow[j+50];
           for(k=-50;k<=50;k++)
		   {
              if(k==0)
				  continue;
              value=sum+a5*pow[k+50];
              p=(__int64)(value*value)%M;
              while(a[p].num&&a[p].val!=value)
				  p=(p+1)%M;
              ans+=a[p].num;
		   }
		}
	 }
       printf("%I64d\n",ans);
   }//while
   return 0;
}//main
=========================================================
二分查找算法
=========================================================
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int M=1000100;
const int N=10010;
__int64 A[M];
__int64 B[M];
__int64 a[N];
__int64 b[N];
__int64 c[N];
__int64 d[N];
__int64 e[N];
int f[105];
int main()
{
	int low,high,mid,i,j,k,len1,len2,m;
	int a1,a2,a3,a4,a5;
	__int64 ans;
	m=0;
	for(i=-50;i<=50;i++)
		if(i!=0)
			f[++m]=i*i*i;
		f[0]=m;
	while(scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)==5)
	{   
		//a1,a2,a3,a4,a5==0有没有都无所谓!一样能过啊！
        if(a1==0&&a2==0&&a3==0&&a4==0&&a5==0)
		{
			printf("10000000000\n");
			continue;
		}
		for(i=1;i<=f[0];i++)
		{
			a[i]=a1*f[i];
			b[i]=a2*f[i];
			c[i]=a3*f[i];
			d[i]=a4*f[i];
			e[i]=a5*f[i];
		}
		len1=0;
		for(i=1;i<=f[0];i++)
			for(j=1;j<=f[0];j++)
				for(k=1;k<=f[0];k++)
					A[++len1]=a[i]+b[j]+c[k];
				A[0]=len1;
		len2=0;
		for(i=1;i<=f[0];i++)
			for(j=1;j<=f[0];j++)
				B[++len2]=d[i]+e[j];
			   B[0]=len2;
		sort(A+1,A+len1+1);
		ans=0;
		for(i=1;i<=B[0];i++)
		{
			//二分查找
			low=1;
			high=A[0];
			while(low<=high)
			{
				mid=(low+high)/2;
				if(B[i]+A[mid]==0)
				{
					ans++;
					break;
				}
				else if(B[i]+A[mid]>0)
					high=mid-1;
				else 
					low=mid+1;
			}
			//中间mid是我们要找的值，可是别忘了，它的两侧还有和他相等的值，也是我们要找的啊！
			//下面的两个循环就是找它的两侧的相同值!
			for(k=mid-1;k>=1;k--)
				if(A[k]+B[i]==0)
					ans++;
				else
					break;
			for(k=mid+1;k<=A[0];k++)
				if(A[k]+B[i]==0)
					ans++;
				else
					break;
		}
		printf("%I64d\n",ans);
	}
	return 0;
}
/*
37 29 41 43 47

654
*/