A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2440 完全平方数 线性筛
发表于: | 分类: Oi | 评论:0 | 阅读:100

最近两天是来填坑的
发现自己莫比鸟斯啥都没写所以先玩玩这个
这个东西可以二分答案,然后问题变成了怎么算小于一个
这个还是蛮简单的
考虑容斥,显然答案等于没有限制的个数-至少一个素数的次数不合法+至少两个素数的次数不和法
计算的时候有多少个是他的倍数的时候就是直接 除法向下取证
但是系数的问题怎么考虑?
我们考虑计算的时候为了避免算重其实算的都是只有k个素数的平方的倍数的东西
这么说不明白,举个栗子,我在算至少一个素数的除数不合法的时候只会计算2,但是不会计算4,6……
在算至少两个的时候只会计算6,10……
你会发现系数其实就是他的$u(x)$

所以
$$ans=\sum\limits_{i=1}^n{u(i)\times \lfloor \frac{x}{i^2} \rfloor}$$
莫比乌斯函数随便筛筛就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e5+5;
const int inf = 2e9+1;
typedef long long LL;
using namespace std;

bool F[N];
int mu[N],prime[N],cnt;

void init(){
    mu[1] = 1;
    register int i,j;
    for(i=2;i<N;++i){
        if(!F[i]) prime[++cnt] = i, mu[i] = -1;
        for(j=1;prime[j]*i<N;++j){
            F[i*prime[j]]=1;
            if(i%prime[j] == 0) break;
            mu[i*prime[j]] = -mu[i];
        }
    }
}

inline int calc(int x){
    int ans = 0;
    for(int i=1;i*i<=x;++i)
        ans += mu[i]*x/(i*i);
    return ans;
}

int main(){ init();
    int T;cin >> T; while(T--){
        LL l = 1, r = inf;
        int k; cin >> k;
        while(l < r){
            int mid = (l+r)>>1;
            if(calc(mid) >= k) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP