abc384f 口糊

__ryp__ · 2024-12-14 21:39:25 · 个人记录

设两个数为 u, v，且 u = 2^{k_1}p_1, v = 2^{k2}p_2, p_1 \equiv p_2 \equiv 1 \mod 2。

两种情况。不等和相等。对于不等的，钦定 k_1 \lt k_2，那么 u + v = 2^{k_1} (p_1 + p_2 2^{k_2-k_1})。由于 p_1 奇，后面偶，所以贡献就是直接加起来。

然后就是相等。考虑到很恶心的是我们不知道这俩东西加起来会除多少个 2。暴力枚举 k_1 （k_2），再暴力枚举一个 k，表示 u + v = 2^k p 其中 p 奇。由于值域 10^7 直接开桶维护数量以及和。但是恶心的是这么算会重，于是做一个唐的没边的容斥。属于是高射炮炮决蚊子，张成泽馋死了。