首页 > 代码库 > Bzoj1041--Haoi2008圆上的整点
Bzoj1041--Haoi2008圆上的整点
对于一个半径为n的圆，圆上整点显然是满足x^2+y^2=n^2的x，y的整数解
由于圆的对称性，我们只有考虑第一象限上的整点，最后乘4再加上坐标轴上4个点即为所求
我们将上式变化一下不难得到:
y^2=n^2-x^2=(n+x)(n-x)
设d为gcd(n+x,n-x),A=(n-x)/d,B=(n+x)/d.
y^2=d^2*A*B
因为我们只考虑x>0的情况，所以显然A!=B，且因为d为gcd(n+x，n-x），所以gcd(A,B)=1
则有A，B均为完全平方数，不妨设A=a^2，B=b^2。
如果我们将A，B相加可以得到:
a^2+b^2=(n+x)/d+(n-x)/d=2*n/d
观察上式发现上式成立时2*n必然可以整除d
由此我们可以在sqrt(2n)的时间内去枚举k
对于每个枚举出来的2*n的约数，我们要考虑两个数，即d=k或d=2*n/k。
因为A<B所以显然有a<b
那么a^2+b^2>2*a^2 ==> d>2*a^2 ==> a<sqrt(d/2)
至此，我们只用对于d=k,d=2*n/k分别去枚举a,在算出对应的b是否为整数
之后再回代回上式求出A,B检验一下A,B是否互质即可（避免重复）
代码：
#include<bits/stdc++.h>#define LL long long#define MAXN 20000005using namespace std;LL n;int ans;bool check(LL a, LL b) { if(__gcd(a,b)==1) return 1; else return 0;}int main() { scanf("%lld",&n);n<<=1; int lim=sqrt(n); for(int k,t,b,d=1;d<=lim;d++) { if(n%d==0) { k=sqrt(n/2/d); for(int a=1;a<=k;a++) { t=n/d-a*a;b=sqrt(t); if(b*b==t&&a<b) { t=(b*b-a*a)*d/2; if(check(a*a,b*b)) ans++; } } if(d*d!=n){ k=sqrt(d/2); for(int a=1;a<=k;a++) { t=d-a*a;b=sqrt(t); if(b*b==t&&a<b) { t=(b*b-a*a)*n/d/2; if(check(a*a,b*b)) ans++; } } } } } printf("%d",ans*4+4); return 0;}
Bzoj1041--Haoi2008圆上的整点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。