• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CT03 Contest#10 equation 大力打表+讨论

开发技术 开发技术 7小时前 3次浏览

目录
  • 题意
  • 做法
    • 若 d=1
    • 若 d-2
    • 若 d=3
    • 若 d=4
    • 若 d=5
    • 若 d=6
    • 若d>=10
  • 注意点
  • 实现
    • 打表
    • 主程序

好久没做这么爽的打表题了!!

当然,这个讨论要人命。

代码:10KB讨论 + 3KB 表

注:附有打表代码

题意

(a^d+b^d=c^e) 的解数。(c^ele nle 10^{18}),要求 (ege 3,dge p)(p,n) 给定。

做法

注:一个快一点的暴力

假设已知 (c^e),可以枚举一个 (a),并设一个 (b),初始等于 (sqrt[d]{c^e})。随着 (a) 的增加,单调的减少这个 (b) 即可。这样复杂度是不带 (log) 的。

以下说跑的暴力,以及打表程序,都是这个写法

考虑枚举 (e)。由于 (ege 3),这个 (c) 就只有最多1e6种了。

再枚举 (d)。讨论:

若 d=1

答案是 ((c^e-1)/2),显然

若 d-2

用HAOI那个圆上的整点那个题的结论,分解质因数做,就行

先把1e6以内的数的最小质因子筛出来,然后每次分解就是 (log) 的了。

若 d=3

如果 (e=3),由费大,无解

如果 (e=4),脑袋一想,好像解不多。搞一个打表程序一算,诶,只有 600 个解不到。打表!(打表程序注意常数优化,我的跑了5~10min左右)

如果 (e=5),脑袋一想,好像解也不多(有了刚才的经验)。于是继续打表

如果 (e=6),由费大,无解

其实如果 (emod d=0),就一定无解,因为我们可以把 (e) 次方看成是先求 (e/d) 次方,再求 (d) 次方;这样两边都是 (d) 次方,就肯定无解

如果 (e=7),继续打表,这个表小到可以直接用 or 语句来判。(e=8) 同理。

由上结论,(e=9,12,15…) 均无解。

如果 (e=11,13,14,16),易发现,只有一个解。随便写几个if搞搞也行

对于更大的 (e),跑暴力的复杂度就小的可怜了。(O(1e18^{1/17})le 11),再乘 (1e6) 也不是问题

注:其实也有点慢,所以后来我代码里增加了对 (e=3) 的特殊待遇,使得它后来跑的飞快

若 d=4

如果 (e=3) ,只有五个解,拿 or 语句判一下

如果 (e=4,8.12…), 无解

如果 (e=5),打表 —— 后来才发现这个表大小只有 (21)

如果 (e=6),无解 (搜出来)

剩下暴力,复杂度:

[sumlimits_{i^4le n} sqrt[7]{i^4}le int_{1}^{sqrt[4]{n}} i^{frac{4}{7}}=frac{7}{11}sqrt[4]{n}^{frac{11}{7}}=frac{7}{11}n^{frac{11}{28}}
]

毛估估,7e6左右。实际上常数更小。

其实我们可以得到一个比较general的式子,对于d,e,复杂度是

(dfrac{e}{d+e}times n^frac{d+e}{dtimes e})

若 d=5

如果 (e=3),同样打表

如果 (e=4),搜一下发现无解

如果 (e=5,10,15…),无解

如果 (e=6),一看只有 (3) 个解,判一下即可

剩下暴力。

复杂度是 (dfrac{7}{12}times n^{frac{12}{35}}),更小

注意到这个东西随着 (d) 的增大是单减的

若 d=6

就像上面的一样,要打表就打表,复杂度够了就暴力,一直搞到8,9左右

若d>=10

直接暴力,飞快

注意点

打表程序:要用一下上面那个小trick

注意double的精度(如果用pow开根),或者手写二分开根

注意不要爆long long

(我是因为这两条,考场只有90)

考场调这种题,要冷静,合理分配时间

实现

打表

co↑co↓

主程序

co↑co↓


程序员灯塔
转载请注明原文链接:CT03 Contest#10 equation 大力打表+讨论
喜欢 (0)