正解:容斥/杜教筛+二分

解题报告:

传送门$QwQ$

首先一看这数据范围显然是考虑二分这个数然后$check$就计算小于等于它的不是讨厌数的个数嘛.

于是考虑怎么算讨厌数的个数?

看到这个讨厌数说,不能是完全平方数的倍数,不难想到可以理解为将$x$质因数分解后不存在指数大于1的情况.

这时候自然而然能联想到莫比乌斯函数?因为根据定义有,只有质数大于1时等于0其他时候为$\pm 1$.

所以答案就$\sum (\mu(i))^2$.杜教筛就好(因为,我,不会杜教筛,所以一句话就带过去了$kk$,可能等我学了杜教筛会来补锅的趴,,?$QwQ$

法二考虑容斥,即答案=总数-一个质因子的平方的倍数+两个不同质因子的平方的倍数-三个不同质因子的平方的倍数...

不解释了趴我$jio$得还挺显然的$QwQ$

考虑怎么求呢?再次想到莫比乌斯函数的特殊性质,考虑枚举这个平方根$i$,贡献显然就$\frac{n}{i^2}$.考虑系数?发现系数取决于质因子的个数的奇偶性,依然根据莫比乌斯函数的定义有,质因子个数为奇数时为负一,质因子个数为偶数是为正一.且质因子质数大于1时等于0保证了一定是不同质因子.

综上,可以得到答案$ans=\sum_{i=1}^{i^2\leq n}\mu(i)\cdot \frac{n}{i^2}$

$over$?

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define fi first

#define sc second

#define gc getchar()

#define mp make_pair

#define int long long

#define P pair<int,int>

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=1e6+;

int n,m,miu[N],pr[N],pr_cnt;

bool is_pr[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void pre()

{

    miu[]=;

    rp(i,,N-)

    {

        if(!is_pr[i])pr[++pr_cnt]=i,miu[i]=-;

        rp(j,,pr_cnt)

        {

            if(i*pr[j]>N-)break;;is_pr[i*pr[j]]=;

            if(!(i%pr[j])){miu[i*pr[j]]=;break;}

            miu[i*pr[j]]=-miu[i];

        }

    }

}

il int check(ri x)

{

    ri ret=;

    for(ri i=;i*i<=x;++i)ret+=miu[i]*(x/i/i);

    return ret;

}

signed main()

{

    //freopen("4318.in","r",stdin);freopen("4318.out","w",stdout);

    ri T=read();pre();

    while(T--)

    {ri K=read(),l=,r=K<<;while(l<r){ri mid=(l+r)>>;if(check(mid)>=K)r=mid;else l=mid+;}printf("%lld\n",l);}

    return ;

}

巴特西

洛谷$P4318$ 完全平方数容斥+二分

正解:容斥/杜教筛+二分

解题报告:

最新文章

热门文章

巴特西

洛谷$P4318$ 完全平方数 容斥+二分

正解:容斥/杜教筛+二分

解题报告:

最新文章

热门文章

洛谷$P4318$ 完全平方数容斥+二分