求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。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 ;
}
04-30 11:27