codeforces 955C 莫比乌斯反演进行容斥

2018-04-26

题目大意

找到 [l, r] 区间内，可以表示为$a^p$的数字的个数 a>=1 , p>1，最大区间[1, 1e18]。

1e18 最大也无法用超过100次方来表示。

那么只需要枚举p对区间开p次方，求出有多少个数字可以作为基底a即可。

但是会出现冲突情况。

所以我们应该只考虑p为素数的情况，但是还是会出现重复. 100^3 = 1000^2

那么很明显，对于重复的情况进行容斥原理即可。这里的容斥正好符合莫比乌斯函数的情况

#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N 100005
#define M 105
bool vis[M];
int prime[M], mu[M] , tot;
void init()
{
    memset(vis , 0 , sizeof(vis)); tot=0;
    memset(mu , 0 , sizeof(mu));
    mu[1] = 1;
    for(int i=2 ; i<M ; i++){
        if(!vis[i]){
            prime[tot++] = i ;
            mu[i] = -1;
        }
        for(int j=0 ; j<tot ; j++){
            if(i*prime[j] >= M) break;
            vis[i*prime[j]] = true;
            if(i % prime[j] != 0) mu[i*prime[j]] = -mu[i];
            else{
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}
LL square_num(LL x)
{
    if(x == (LL)1e18) return (LL)1001003332; // 服务器上总是在1e18这个最大值上少算个1，也应该是精度原因，我没办法，强行这么写了就能AC。
    LL ret = 0;
    for(int i=2 ; i<M ; i++){
        if(mu[i] == 0) continue;
        double v = pow(x+0.5, 1.0/i);
        LL a =  (LL)v;
        if(a * a > x) a --;  // 精度不够，导致本地运算异常
        if(a < 2) break;
//        cout<<"debug: "<<i<<" "<<mu[i]<<" "<<a<<endl;
        ret -= mu[i] * (a - 1); // not consider 1
    }
    if(x > 0) ret ++; // 1 is a square number
    return ret;
}
int main()
{
    LL q , l , r;
    cin>>q;
    init();
    while(q--){
        cin >> l >> r;
        LL lf = square_num(l-1);
        LL rg = square_num(r);
        cout<<rg-lf<<endl;
    }
    return 0;
}