T1 方程

描述

给出非负整数 \(N\) ，统计不定方程 \(X+Y^2+Z^3=N\) 的非负整数解 \((X,Y,Z)\) 的数量。

输入

输入数据，包含一个非负整数 \(N\)。

输出

输出数据，包含一个非负整数表示解的数量。

数据范围

40%的数据，\(N<=10000\)
60%的数据，\(N<=10^8\)
100%的数据，\(N<=10^{16}\)

分析

看到这个数据范围，应该只能从 \(Z\) 开始枚举。

移项后可得 \(X+Y^2=N-Z^3\) ，所以 \(0\leq Y\leq\sqrt{N-Z^3}\)。

注意，我们对于这个 \(Y\) 的具体值不感兴趣，我们只关心有多少个，而此时有 \((\sqrt{N-Z^3}+1)\) 个合法的 \(Y\)。此时， \(X=N-Z^3-Y^2\) ，显然也是一个非负整数。

所以，我们只需要从小到大枚举 \(Z\)，将 \((\sqrt{N-Z^3}+1)\) 添加到 \(ans\) 即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,ans;
int main(){
	scanf("%lld",&n);
	for(ll z=0;z*z*z<=n;z++)
		ans+=ll(sqrt(n-z*z*z))+1ll;
	
	printf("%lld",ans);
	return 0;
	
}