BZOJ1041 HAOI2008圆上的整点（数论）

　　求x²+y²=r²的整数解个数，显然要化化式子。考虑求正整数解。

　　y²=r²-x²→y²=(r-x)(r+x)→(r-x)(r+x)为完全平方数→(r-x)(r+x)/d²为完全平方数，d=gcd(r-x,r+x)→(r-x)/d·(r+x)/d为完全平方数，gcd((r-x)/d,(r+x)/d)=1→(r-x)/d和(r+x)/d均为完全平方数→(r-x)/d+(r+x)/d=2r/d为整数，即d|2r

　　于是我们可以以√n的复杂度枚举d，然后枚举√(r-x)/d，检验一下是否满足之前推导中的条件即可，再加上坐标轴上和其余象限的答案。

　　这样的复杂度并不显然，不过感觉上明显低于线性，并且一个数的因数个数是有比较优秀的上界的：n^{1.066/ln(ln n)}。http://vfleaking.blog.163.com/blog/static/174807634201341913040467/

　　还有O(分解质因数)的神仙做法，似乎将素数拓展到了复平面，并不可能懂。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define ll long long

int n,ans=;

ll m;

ll gcd(ll n,ll m){return m==?n:gcd(m,n%m);}

void solve(ll x)

{

    if (x>=n) return;

    for (int i=;i*i*x<=n;i++)

    {

        int a=i*i;

        if (gcd(a,m/x-a)==&&((ll)sqrt(m/x-a))*((ll)sqrt(m/x-a))==m/x-a) ans++;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj1041.in","r",stdin);

    freopen("bzoj1041.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();m=1ll*n<<;

    for (ll i=;i*i<=m;i++)

    if (m%i==)

    {

        solve(i);

        if (i*i<m) solve(m/i);

    }

    cout<<(ans+<<);

    return ;

}

巴特西

BZOJ1041 HAOI2008圆上的整点（数论）

最新文章

热门文章