题目
Let’s denote as L(x, p) an infinite sequence of integers y such that gcd(p, y) = 1 and y > x (where gcd is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of L(x, p) are 1-indexed; for example, 9, 13 and 15 are the first, the second and the third elements of L(7, 22), respectively.
You have to process t queries. Each query is denoted by three integers x, p and k, and the answer to this query is k-th element of L(x, p).
Input
The first line contains one integer t (1 ≤ t ≤ 30000) — the number of queries to process.
Then t lines follow. i-th line contains three integers x, p and k for i-th query (1 ≤ x, p, k ≤ 106).
Output
Print t integers, where i-th integer is the answer to i-th query.
Examples**
Input1
|
|
Output1
|
|
Input2
|
|
Output2
|
|
题目大意
L(x,p) 表示一个y的从小到大的有序列表,y满足两个条件 gcd(y,p) = 1且 y > x。
多次询问,每次询问给定一个x , p , k ([1, 1e6])
输出是找到L(x,p) 第k个位置上的数字,下标从1开始。也就是找到第k个比x大且和p互素的数字。
解题思路
很明显的答案满足二分查找的要求。
那么我们只需要知道在[1, n] 的范围内与p互质的数字个数。这就很容易转化成莫比乌斯式子求解了
$$
\sum_{x=1}^m [gcd(x,n) = 1] = \sum_{x=1}^m\sum_{d|x\&d|n}\mu(d) = \sum_{d}[d|n]\sum_{x=1}^m[d|x] = \sum_{d}[d|n]\lfloor x/d \rfloor
$$
那么只要一开始求解出p的所有因子列表即可,询问次数不超过3000,二分的复杂度是log(n)的,因子个数不超过$\sqrt n$。
所以总的时间复杂度是$3000 \log n \sqrt n$
代码实现
GNU C++11 763 ms
|
|