求 a^2+b^3=n 的正整数解个数

学术版

听取MLE声一片 @ 2023-02-08 21:49:17

本题难度很高，禁止无意义回复。

没有原题，不要问。

多测，大概为 $10^4$，也就是要求快于 $n^{\frac{1}{3}}$ 的做法。已推出结论：设一个虚数的实部和虚部分别为 $u,v$，那么： ``` a=72u(3u^2-v^2) b=-12(3u^2-v^2)=sqrt(n/3)/(-2v) ``` 尝试过的方法：椭圆曲线，虚数，同余。请有一定了解后再回复，禁止无意义回复。

by 听取MLE声一片 @ 2023-02-08 21:51:58

合作的大佬@donghanwen1225 对于题目问题也可以问他。

by Sol1 @ 2023-02-08 22:24:44

《没有原题，不要问》

by 听取MLE声一片 @ 2023-02-08 22:35:27

@Sol1 我超，谢谢。我看看

by 听取MLE声一片 @ 2023-02-08 22:36:46

但是好像没用，不能做到三分之一次方以内。

by Sol1 @ 2023-02-08 22:50:55

@听取MLE声一片好像确实没说怎么做...有可能是open的，这个是你们在模拟赛里面碰上的题吗，如果是的话可以联系出题人让他把自己的大名登上oeis（

by esquigybcu @ 2023-02-08 22:52:06

@听取MLE声一片这篇回答中提到可以用 Stern-Bercot tree 快速枚举这个方程的解。这是 O(\text{解数}\cdot \log n) 的。按照 OEIS 上来看，解数应该是很小的。

by Nathaly @ 2023-02-08 22:54:50

@esquigybcu 咋枚举的啊

by Eznibuil @ 2023-02-08 22:58:37

@esquigybcu 兄弟您 Stern-Brocot 都打错了……而且我并没想到怎么枚举……

by esquigybcu @ 2023-02-08 23:01:51

@Alan_Zhao 我也不知道，反正评论区里答主 claim 说可以这么枚举（

by Nathaly @ 2023-02-08 23:04:47

@esquigybcu 二次方和三次方差别还是很大的吧……

| 下一页