ACM 106 Fermat vs. Pythagoras
作法:數學解.
畢達哥拉斯跟費瑪...建表唄
勾股數的條件
/* abc為三邊 m > n 、 m 和 n 均是正整*/
/*a = m^2 -n^2, */
/*b = 2mn, */
/*c = m^2+n^2*/
之後再建表搜尋費瑪的...
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
int gcd(int a,int b)
{
int temp;
while(a%b)
{
temp=a;
a=b;
b=temp%b;
}
return b;
}
char flag[10000001]={0};
main()
{
int nn;
while (scanf("%d",&nn)==1&&nn!=0)
{
int ans=0,ans2=0;
int n,m,a,b,c;
for(n=1;n<1000;n++)
{
for(m=n+1;m<1000;m=m+2)
{
if (gcd(m,n)>1) continue;
c=m*m+n*n;
if(c>nn) break;
ans++;
for(a=0;a<nn;a++)
{
if(c*a>nn) break;
flag[a*(m*m+n*n)]=1;
flag[a*(2*m*n)]=1;
flag[a*(m*m-n*n)]=1;
}
}
}
for(a=1;a<=nn;a++)
{
if(flag[a]==1) ans2++;
flag[a]=0;
}
printf("%d %d\n",ans,nn-ans2);
}
return 0;
}
/* abc為三邊 m > n 、 m 和 n 均是正整*/
/*a = m^2 -n^2, */
/*b = 2mn, */
/*c = m^2+n^2*/