盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5297 Y sequence(数论,容斥,迭代)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5297

题意

定义一个序列,其中每一个数都不能表示为a^b(其中2≤b≤r)。现在给定n和r。问排在第n位的数字是多少?
其中n≤2*1e18,2≤r≤62

思路

乍一看这道题完全没有想法。
其实可以先考虑任意给定一个数字n,求n排在第几位。这就需要把2, 3, …… r次方的数都删去。可以发现删去2次方时,4次方,8次方,以此类推的都被删过了。所以我们只需要考虑质数即可。
当然,这样还是有问题,比如6次方在删2次方、3次方时被多干掉一次,所以需要用容斥定理。我之前一直以为容斥要用dfs来搜。今天学到了一个新姿势。详细见代码
需要注意的细节是1肯定不行,所以最后要删去。
求出来数字n是多少位之后,就可以搞了。常见的想法是二分,但是这道题目的区间特别大,二分并不合适。
这里采用了迭代的思想,假设当前now排在第m位,距离第n位还有n-m位,那么就再算now+m排在第几位,以此类推直到找到最后的答案。

代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
#define pb push_back
typedef long long ll;
using namespace std;
ll n;
int r;
vector<ll> p;
vector<ll> f;
void getprime() {
for (int i = 2; i <= 61; i++) {
bool flag = true;
for (int j = 2; j <= sqrt(i + 0.5); j++) if (i % j == 0) {
flag = false;
break;
}
if (flag) p.push_back(-i);//, cout<<i<<endl;
}
}
void getfac() {
f.clear();
for (int i = 0; i < p.size() && abs(p[i]) <= r; i++) {
int num = f.size();
for (int j = 0; j < num; j++) {
if (abs(f[j] * p[i]) > 63) continue; //2的64次就已经超过了最大值
f.push_back(f[j] * p[i]);
}
f.push_back(p[i]);
}
}
ll cal(ll n) {
ll res = n;
for (int i = 0; i < f.size(); i++) {
ll p = (ll)pow(n + 0.5, 1.0 / abs(f[i])) - 1;
if (f[i] > 0) res += p;
else res -= p;
}
return res - 1;
}
int main () {
getprime();
int t;
scanf("%d", &t);
while(t--) {
scanf("%I64d%d", &n, &r);
getfac();
ll now = n, ans;
while(1) {
ans = cal(now);
if (ans == n) break;
now += n - ans;
}
printf("%I64d\n", now);
}
return 0;
}
/*
10
20000000000000000 63
*/

更新日志

  • 14238099 2015-07-29 15:31:11 Accepted 5297 358MS 1580K 1221 B G++ SIO__Five