-

以下、除算は全て整数の範囲で切り捨てで行うものとする

・2変数への帰着
「m>nかつ偶奇が異なり互いに素」である組(n,m)から(m^2-n^2,2nm,m^2+n^2)により原子ピタゴラス数への全単射がある。
よって、そのような全ての組(n,m)についてのN/(2m^2+2nm)の和を取れば良い。
m>nの条件がめんどくさいのでm=n+sと変数変換して分母は2m(n+m)=2(n+s)(2n+s)となる。gcdの条件はそのまま(n,s)が互いに素であること。偶奇の条件はsが奇数であること。sの偶奇を気にせず和を取ったものから、sが偶数のものを差し引けば良い。以下、差し引くことを考える。
偶奇を考慮に入れずに計算したものをf(N)とおく。すなわち、f(N)を「互いに素である(n,s)に関するN/(2(n+s)(2n+s))の和」とする。
sが偶数のものはs=2tとおいて「互いに素である(n,2t)に関するN/(2(n+2t)(2n+2t))の和」である。これをg(N)とおく。
さらに「互いに素である(n,t)に関するN/(2(n+2t)(2n+2t))の和」をh(N)とおく。g(N)との違いは、gcdの条件が(n,2t)から(n,t)になったところ。これは元の条件よりゆるくなっている。具体的には、「nが偶数かつ互いに素である(n,t)」の組が含まれるようになっている。ここでn=2uとおけば、そのような組に対する和は「互いに素(u,t)に関するN/(2(2u+2t)(4u+2t))の和」となる。和を取る対象を整理すると(N/4)/(2(u+t)(2u+t))となり、これはf(N/4)に等しい。
求めるものはf(N)-g(N)であり、g(N)=h(N)-f(N/4)なので、結局求めるものはf(N)-h(N)+f(N/4)-h(N/4)+f(N/16)-h(N/16)+……となる。fとhは分母の係数が微妙に違うだけでほとんど同様に計算できるので、以下ではfを考える
・gcdの部分を包除原理する
fからgcdの条件を外したものをFとすると、f(N)=Σμ(d)F(N/d^2)であることがわかる。よって、各dについてF(N/d^2)が求まれば良い。
・F(n)を求める
F(n)=Σn/hogeの形をしているので、hogeで上下に分けることを考える。
hoge≦vの範囲は愚直にやってO(v)となる。それ以上の範囲は、n/hogeの値に注目することで「hoge≦n/iを満たす(x,y)の個数の数え上げ」に帰着できる。この数え上げはxを全探索することでO(√(n/i))でできるので、全てのiについてO(n/√v)で求まる。よって、v=O(n^(2/3))ととれば全体でO(n^(2/3))となる。
・で計算量は？
F(n)はO(n^(2/3))で求まることがわかった。求めたいf(N)=ΣF(N/d^2)はというと、F(N/d^2)をそれぞれをO((N/d^2)^(2/3))で求めることでO(N^(2/3))となる。最終的に求めたかったΣf(N/4^k)も、等比数列の和を考えると定数倍の違いであり、O(N^(2/3))で求まる。
・さらなる改善
「この数え上げはxを全探索することでO(√(n/i))でできるので」と書いた部分は、凸包テクによりO((n/i)^(1/3))になるので、v=O(N^(3/5))とすることで、F(n)はO(n^(3/5))で求まり、全体でO(N^(3/5))となる。