Project Euler 804

题目

Balanced Numbers

Let \(g(n)\) denote the number of ways a positive integer \(n\) can be represented in the form:

\[x^2+xy+41y^2\]

where \(x\) and \(y\) are integers. For example, \(g(53)=4\) due to \((x,y) \in \{(-4,1),(-3,-1),(3,1),(4,-1)\}\).

Define \(\displaystyle T(N)=\sum_{n=1}^{N}g(n)\). You are given \(T(10^3)=474\) and \(T(10^6)=492128\).

Find \(T(10^{16})\).

解决方案

令\(N=10^{16},F(x,y)=x^2+xy+41y^2\)。不难证明，\(F(x,y)>0\)恒成立，除了\((x,y)=(0,0)\)。

因此，\(T(N)\)的值就相当于有多少个非原点\((x,y)\)，满足\(F(x,y)\le N\)。

固定\(y\)，那么可以将\(F(x,y)\)写成顶点式：

\[F(x,y)=\left(x+\dfrac{y}{2}\right)^2+\dfrac{163y^2}{4}\]

枚举\(y\)，然后解不等式\(F(x,y)\le N\)即可，直到方程无解。

为了排除\((0,0)\)的情况，单独考虑\(y=0\)时的情况，这时有\(2\lfloor\sqrt{N}\rfloor\)个解。

否则，区间\(\left[\dfrac{-y-\sqrt{4N-163y^2}}{2},\dfrac{-y+\sqrt{4N-163y^2}}{2}\right]\)种的所有整数解都是答案，直接统计即可。

代码

#include <bits/stdc++.h>
# include "tools.h"
typedef long long ll;
using namespace std;
const ll N=1e16;
int main(){
    ll ans=int_sqrt(N)*2;
    for(ll i=1,d2;(d2=N*4-i*i*163)>=0;i++){
        ll r=-i+int_sqrt(d2);
        if(r<0&&r&1) --r;
        r>>=1;
        ll l=-i-r;
        ans+=(r-l+1)*2;
    }
    printf("%lld\n",ans);
}