「Codeforces 955 - C. Sad powers」解题报告

题目信息

题目分析

描述

给定 $Q$ $(1≤Q≤10^5)$ 组询问 $(L,R)$ $(1≤L≤R≤10^{18})$。
对每组询问回答有多少个 $x$ $(L≤x≤R)$ 满足存在 $a>0,$ $p>1$ 使得 $x=a^p$。
比如样例询问 $(1,4)$,结果为 $2$ $(1=1^2,$ $4=2^2)$。
时间限制:2s。
空间限制:256M。

解题思路

首先看到是个多组独立的区间询问问题,第一反应是看看能不能做预处理+离线询问。
然而看到数据范围已经达到了long long的量级,就还是只能考虑在线算法。
于是这就要求用非常高效的做法解决每一次询问,初步的想法是可以枚举a或者p。
a可能的范围从1到 $\sqrt{10^{18}}=10^9$,而p可能的范围从2到 $\log_2 10^{18} \approx 60$。
当然a为1的时候p理论上可以达到无穷大,但这种情况只可能在判断x为1的时候,也就是L必须为1。
因此只需要在L为1的时候特判一下,x为1显然满足,除此之外的情况下p不可能超过60。
那么显然枚举p比枚举a更可行,对每个枚举的p来说:
最小满足的a为 $a_\min = \lceil \sqrt[p]{L} \rceil$,最大满足的a为 $a_\max = \lfloor \sqrt[p]{R} \rfloor$。
$a_\min$ 与 $a_\max$ 中间包含的a一定都满足要求,只需注意一点:
L、R靠的太近时可能出现 $a_\min>a_\max$,那么对这个p来说就没有a满足要求。
此时考虑重复统计的问题,首先能想到的是只需要枚举质数p就好。
因为满足要求的x如果在某个合数p中能统计到,那么在p的质因数上也能统计到。
但此时还有一个问题,如果某个满足要求的x是某个a的合数p次方,这个p有大于等于2个质因数。
那么这个x还是会在枚举p的这几个质因数时分别统计到,比如 $64=8^2=4^3$。
因此还需要对60以内的质数做一下容斥,因为范围比较小,最多算到第三重。
稍微笔算一下就能把需要考虑减去的两两相乘与需要再加上的3个质因数相乘的结果预处理好。
这个问题理论上也就完美解决啦。

细节处理

求 $a_\min$ 与 $a_\max$ 时需要求p次方根,能想到的方法是利用cmath库的pow函数求$1 \over p$次方。
但是pow的精度非常有限,在处理long long级别的数值时候会出现精度问题。
此时有两个解决方法,一是用二分的方法找到精确的整数解:
对每个枚举的p,这种方法的时间复杂度为二分复杂度×求幂复杂度。
假设数值范围(L、R的范围)为M(即 $1≤M≤10^{18}$),并且考虑使用快速幂。
则每次询问p的时间复杂度为 $O(\log M \cdot \log \log M)$。尝试此方法后发现TLE了。
第二种方法是依旧使用pow,但是需要手动矫正因精度误差带来的问题。
不负责任的尝试,发现在这道题目的数据范围约束下pow结果的误差在±1以内。
于是就有了以下的做法(当然实际中是通过以下的做法发现了其误差范围):
算出pow的结果按指定方向取整得到的a备选值res后,计算res-1与res+1作为返回的a是否满足要求。
最终返回调整之后相应的a,计算是否满足要求的时候也考虑使用快速幂。
此时每次询问p的时间复杂度为 $O(\log M + \log \log M)$。
虽然后者项已经算是前者项的低阶项了,不过这道题目确实很卡时间,还是将所有影响时间的因素都考虑进去。
显然这样做会比之前第一种方法快,也在2s的时限内用1s+惊险的AC了。
此外,计算快速幂时可能会溢出,因为范围已经是long long级别的了,只能通过符号的变换来判断是否溢出。
如果每次倍增的辅助数或者中间结果中的任一个算出来小于等于0就说明已经溢出了。

复杂度分析

假设数值范围为M,上面分析了每次询问p的时间复杂度,p的枚举量是 $\log M$ 的。
因此总的时间复杂度为 $O(N(\log M + \log \log M)\log M) \Rightarrow O(N \log^2 M)$。
空间复杂度为 $O(\log M)$。
其实理论上空间复杂度只需 $O(1)$,这里考虑了存放通过容斥原理预处理的需要枚举的p值。

AC代码(Microsoft Visual C++ 2010)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

const int N_P = 19;
const int N_M = 17;
const long long MAXLL = 0x7FFFFFFFFFFFFFFFLL;

const int plus_p[N_P] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
30, 42
};

const int minus_p[N_M] = {
6, 10, 14, 22, 26, 34, 38, 46, 58,
15, 21, 33, 39, 51, 57,
35, 55
};

long long my_pow(long long a, int k)
{
long long res = 1, h = a;
while (k) {
if (k & 1) {
res *= h;
}
if (h <= 0 || res <= 0) {
return MAXLL;
}
h *= h;
k >>= 1;
}
return res;
}

long long find_left(long long l, int k)
{
long long res = (long long)ceil(pow(l, 1.0 / k)) + 1;
while (my_pow(res - 1, k) >= l) {
res--;
}
return res;
}

long long find_right(long long r, int k)
{
long long res = (long long)floor(pow(r, 1.0 / k)) - 1;
while (my_pow(res + 1, k) <= r) {
res++;
}
return res;
}

void calc(long long l, long long r)
{
long long ans = 0;
if (l == 1) {
ans++;
l++;
}
for (int i = 0; i < N_P; ++i) {
int p = plus_p[i];
long long min_a = find_left(l, p);
long long max_a = find_right(r, p);
if (min_a <= max_a) {
ans += max_a - min_a + 1;
//cout << "+: " << p << ' ' << min_a << ' ' << max_a << endl;
}
}
for (int i = 0; i < N_M; ++i) {
int p = minus_p[i];
long long min_a = find_left(l, p);
long long max_a = find_right(r, p);
if (min_a <= max_a) {
ans -= max_a - min_a + 1;
//cout << "-: " << p << ' ' << min_a << ' ' << max_a << endl;
}
}
printf("%I64d\n", ans);
}

int main()
{
int q;
cin >> q;
long long l, r;
for (int i = 1; i <= q; ++i) {
scanf("%I64d%I64d", &l, &r);
calc(l, r);
}
return 0;
}

解题心得

在比赛之外做的,花了很久时间才做到AC,如果是比赛当场做估计是做不出来的。
这道题难度不是很大,但是会造成WA的细节非常多。
如果放宽时间的限制,笔者认为用二分寻找 $a_\min$ 与 $a_\max$ 才是这道题最优雅的解法。