题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5297
题意：给你一个所有正整数的序列，然后去掉满足x^(2~r)的所有数（x为所有正整数，r>=2题目给出），问你现在这个序列的第n个数是什么
解：首先想到写一个函数func(y)，它可以计算出给定数字y是序列中第几个数，这样我们大概可以二分答案~（事实上会TLE，得用迭代法，当然迭代的话也是用这个函数）
那么如何实现func：
首先想去掉满足x^2的所有数，我们可以用pow(y, 1/2)计算出y以下有多少个满足x^2的数
然后去掉满足x^3的，注意到这里x^6的数被去除了两次，那么我们可以进行容斥，这样func就实现了
实现了func以后，开始二分，结果各种TLE，迭代就过了（具体看代码，感觉迭代的复杂度就是玄学~）
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/8/3 星期一 14:44:48
* File Name: 233.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; long long n;
int r;
vector<int> tmpTable;
vector<int> table;
long long cal(long long x, long long power) {
return pow(double(x+0.5), 1.0/power)-;
}
void init() {
table.clear();
for(int i=; i<(int)tmpTable.size() && -tmpTable[i]<=r; i++) {
int a=tmpTable[i];
int tmp=table.size();
for(int j=; j<tmp; j++) {
int b=table[j];
if(abs(a*b)<=) table.push_back(a*b);
}
table.push_back(a);
}
}
long long func(long long x) {
if(x==) return ;
long long res=x;
for(int power : table) {
long long tmp=pow(double(x+0.5), 1.0/abs(power))-;
if(power<) res-=tmp;
else res+=tmp;
}
return res-;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
vector<int> vis(, );
for(int i=; i<; i++) {
if(vis[i]!=) continue;
tmpTable.push_back(-i);
for(int j=i+i; j<; j+=i) {
vis[j]=;
}
}
int T;
scanf("%d", &T);
while(T--) {
scanf("%I64d%d", &n, &r);
init();
long long ans=n, tmp=-;
while(tmp!=n) {
tmp=func(ans);
ans+=n-tmp;
}
printf("%I64d\n", ans);
}
return ;
}
hdu 5297