Fermat vs. Pythagoras看有没有更好的方法？

作者：心剑菩提来源：不详发布时间：2008/08/04 发布人：admin

心剑菩提 发布留言 2008-8-3 16:46

Fermat vs. Pythagoras看有没有更好的方法？

著名的費馬大定理是指：當n>2時，xn+yn=zn 無整數解，這邊我們要處理的問題跟費馬大定理有點關係。

給你一個正整數 N，你的任務是算出兩個與方程式 x2+y2=z2 的解相關的數字。( 0 < x < y < z <= N )

第一個數字是互質的數對(triples) (x,y,z) 數目。互質是指 x、y、z 沒有大於 1 的公因數。第二個數字p是在小於等於 N 的數字內不屬於任何數對 (x,y,z) 的正整數總數，這邊 x、y、z不需要互質。

例如，N=10，可找到一組互質數對 (3,4,5) 及一組不互質的數對 (6,8,10)， 1、2、7、9 共 4 個數字沒用到。所以N=10要輸出1與4。

Input

輸入含有多組測試資料，每組測試資料一列，有一個正整數 N （1 <= N <= 1000000）

Output

輸出一列，含兩個整數，如題目所述，數字中間以一個空白字元分隔。

Sample Input
10
25
100
500
1000000
Sample Output
1 4
4 9
16 27
80 107
159139 133926

心剑菩提 发布留言 2008-8-3 16:47

时间太长

#include"stdio.h"
#include"math.h"
#include"string.h"
int mark[1000000];
int prime(int x,int y)
{
for(int i=2;i<=x;i++)
{
   if(x%i==0&&y%i==0)  return 0;
}
return 1;
}

int main()
{
int n;
int m1,m2;
int x,y,z;
int cnt;
while(scanf("%d",&n)!=EOF)
{
   memset(mark,0,sizeof(mark));
   cnt=0;m1=0;m2=0;
   for(x=3;x<=n;x++)
   {
      for(y=x+1;y*y+x*x<=n*n;y++)
      {
         z=(int)floor(sqrt((double)(x*x+y*y)));
         if(x*x+y*y==z*z)
         {
            if(prime(x,y)&&prime(z,y)&&prime(x,z))
            cnt++;
            mark[x]=1;
            mark[y]=1;
            mark[z]=1;
         }
         if(x*x+y*y==(z+1)*(z+1))
         {
            if(prime(x,y)&&prime(z+1,y)&&prime(x,z+1))
            cnt++;
            mark[x]=1;
            mark[y]=1;
            mark[z+1]=1;
         }
      }
   }
   for(x=1;x<=n;x++)
   {
      if(mark[x]==0)    m1++;
   }
   printf("%d %d\n",cnt,m1);
}
return 0;
}

页: [1]

特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！

[] [返回] [打印] [收藏] [评论]

上一篇代码：哪位大侠给我发一个好用的TC2.0，我找的一些都不能用

下一篇代码：【已解决】请解释第三个printf,谢谢!

Fermat vs. Pythagoras看有没有更好的方法？

Fermat vs. Pythagoras看有没有更好的方法？

时间太长

精品推荐

代码分类

阅读排行

相关代码