题目连接:http://poj.org/problem?id=1305
题目是叫我们去求小于n的勾股原数组的个数
熟悉数论的同学或许记得那个本原勾股数组的公式
a=s*t,b=(s*s-t*t)/2,c=(s*s+t*t)/2
其中s>t>=1而且gcd(s,t)==1
参见《数论概论》第二章勾股数组
所以下面的任务就很轻松了,只需要暴力求解就可以了
POJ的数据很弱,所以0秒就可以AC了
我的代码:
Source Code
Problem: 1305
|
|
User: bingshen
|
Memory: 1140K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<math.h>
#include<string.h>
bool flag[1000005];
__int64 gcd(__int64 a,__int64 b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
int main()
{
__int64 n,s,t,a,b,c,ans1,ans2,i;
while(scanf("%I64d",&n)!=EOF)
{
ans1=0,ans2=0;
memset(flag,0,sizeof(flag));
for(t=1;t<=n;t=t+2)
{
for(s=t+2;s<=n;s=s+2)
{
if(gcd(s,t)!=1)
continue;
a=s*t;
b=(s*s-t*t)/2;
c=(s*s+t*t)/2;
if(c>n)
break;
ans1++;
for(i=1;c*i<=n;i++)
{
flag[i*a]=true;
flag[i*b]=true;
flag[i*c]=true;
}
}
}
for(i=1;i<=n;i++)
if(!flag[i])
ans2++;
printf("%I64d %I64d/n",ans1,ans2);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
这是POJ上算法学习中推荐的50个题目,熟练编写这些程序,将会使算法水平大有调高
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告