P9118题解

Kreado · 2023-03-09 19:23:13 · 题解

题目传送门。

Update 2023/10/16 修改了代码和一些笔误。

思路

我们令 f(i) 表示 x=a^i(x\le N,x_p\not=x_q) 的个数。

令 g(i) 表示 x=a^i(x\le N) 的个数。

很容易得到 g(i)=f(i)+f(2i)+\cdots+f(li),(li\le 100)。

易知 g(i)=\sqrt[i]n。

所以 f(i)=g(i)-f(2i)-f(3i)-\cdots-f(li)。

从后往前容斥即可。

当 a=1 时，a^i 恒等于 1，我们要在容斥过程中减去这部分，统计答案的时候加上 1 的贡献即可。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=110;
const double eps=1e-9;
ll f[Maxn],n,k,ans=1;
int main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=100;i>=k;i--){
        f[i]=pow<long double>(n,1.0/i)+eps-1;
        for(ll j=i<<1;j<=100;j+=i) f[i]-=f[j];
        ans+=f[i];
    }
    printf("%lld",ans);
    return 0;
}