首页 > 代码库 > POJ 1305
POJ 1305
求本原毕达三原组的个数以及不是毕达三元组的数。
这道题需要把规模降下来,由
x=m^2-n^2
y=2mn
z=m^2+n^2
由有x+y<=2*k即(m+n)^2<2k开方后即可把m,n范围缩小,然后枚举
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int Maxn=1000010;bool flag[Maxn];int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}void slove(int n){ int x,y,z; int count=0; memset(flag,false,sizeof(flag)); int t=(int)sqrt(n*2.0); for(int i=1;i<=t;i++){ for(int j=i+1;j<=t;j++){ if(i*i+j*j>n) break; if(2*i*j>n) break; if(i%2!=j%2){ if(gcd(i,j)!=1) continue; x=j*j-i*i; y=2*i*j; z=i*i+j*j; count++; flag[x]=flag[y]=flag[z]=true; for(int k=2;;k++){ if(z*k>n) break; flag[x*k]=flag[y*k]=flag[z*k]=true; } } } } int ac=0; for(int i=1;i<=n;i++) if(!flag[i]) ac++; printf("%d %d\n",count,ac);}int main(){ int n; while(scanf("%d",&n)!=EOF){ slove(n); } return 0;}
POJ 1305
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。