HDU 5297 Y sequence 容斥 迭代

Y sequence

题目连接:

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

Description

Yellowstar likes integers so much that he listed all positive integers in ascending order,but he hates those numbers which can be written as a^b (a, b are positive integers,2<=b<=r),so he removed them all.Yellowstar calls the sequence that formed by the rest integers“Y sequence”.When r=3,The first few items of it are:

2,3,5,6,7,10......

Given positive integers n and r,you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).

Input

The first line of the input contains a single number T:the number of test cases.

Then T cases follow, each contains two positive integer n and r described above.

n<=2*10^18,2<=r<=62,T<=30000.

Output

For each case,output Y(n).

Sample Input

2

10 2

10 3

Sample Output

13

14

Hint

题意

有一个序列,一开始是1,2,3,4,5,....,inf 这样的。

然后这个序列把a^b(1<b<=r)都删除掉了。

现在给你n,r。

问你这个序列的第n项是什么。

题解:

假设我们知道了cal(x)表示包括x在内的x之前这个序列有多少个数。

那么显然我们就可以直接二分乱搞就好了。

然后cal怎么做呢?

x(1/b)就表示x范围内有多少个ab次方的数,然后根据这个容斥一波就好了。

比如你减去了2次方的,减去了3次方的,但是你多减了6次方的,你得加回去。

然后你就做完了。

还有一个问题就是二分会TLE,所以你就只能换成迭代做了……

代码

#include<bits/stdc++.h>
using namespace std;
int prime[100],cnt;
long long n;int m;
vector<int>v;
void init()
{
int tot=2;
while(1)
{
if(tot>100)break;
int flag=0;
for(int i=2;i<tot;i++)
if(tot%i==0)flag=1;
if(flag==0)prime[cnt++]=-tot;
tot++;
}
}
void init2()
{
v.clear();
for(int i=0;-prime[i]<=m;i++)
{
int tot = v.size();
for(int j=0;j<tot;j++)
if(abs(v[j]*prime[i])<=63)
v.push_back(v[j]*prime[i]);
v.push_back(prime[i]);
}
}
long long cal(long long x)
{
long long ra = 0;
for(int i=0;i<v.size();i++)
{
long long tmp = exp(log(x+0.5)/abs(v[i]))-1;
if(v[i]<0)ra=ra+tmp;
else ra=ra-tmp;
}
return x-ra-1;
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%d",&n,&m);
init2();
long long ans = n,tmp = cal(n);
while(tmp<n)
{
ans=ans+n-tmp;
tmp=cal(ans);
}
printf("%lld\n",ans);
}
}
上一篇:Retrofit+OKHttp忽略https证书验证


下一篇:CloudStack 注册模板脚本分析