BZOJ 1041 HAOI2008 圓上的整點 數論

BZOJ 1041 HAOI2008 圓上的整點 數論

題目大意：給定一個半徑為為r的圓x^2+y^2=r^2，求圓上多少個點的坐標為整數

卡了很久的一道題。。。我之前用了兩個公式，理論上可以O(√n)出解，可惜這兩個公式並不能涵蓋所有勾股數。。。

x^2+y^2=r^2

化簡為 y^2=(r-x)(r+x)

我們令d=gcd(r-x,r+x)

則(r-x)/d與(r+x)/d一定互質，二者相乘為完全平方數，則二者一定都為完全平方數

令r-x=d*u^2,r+x=d*v^2

則有u,v互質，u

其中x=d(v^2-u^2)/2

y=d*u*v

r=d*(u^2+v^2)/2

枚舉2r的因數d，對於每個d我們用O[√(r/d)]的時間枚舉u 代入r的計算式得出v^2 計算v^2是否為完全平衡數及u與v是否互質

這樣可以枚舉出一個象限內的整點個數 然後輸出(ans+1)*4即可

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll r,ans;
ll factors[100100];
int tot;
void Get_Factors(ll x)
{
	ll i;
	for(i=1;i*i>r;
	int i;
	ll u;
	Get_Factors(r<<1);
	for(i=1;i<=tot;i++)
	{
		ll d=factors[i];
		for(u=1;u*u<(r+1)/d;u++)
		{
			ll v_2=r*2/factors[i]-u*u;
			if( Is_Square(v_2) )
				if(GCD(v_2,u*u)==1)
					++ans;
		}
	}
	cout<<(ans+1<<2)<