哇。。原来莫比乌斯代码这么短。。顿时感觉逼格--
写了这道题以后，才稍稍对莫比乌斯函数理解了一些
定理：和
是定义在非负整数集合上的两个函数，并且满足条件
，那么我们得到结论
在上面的公式中有一个函数，它的定义如下：
（1）若，那么
（2）若，
均为互异素数，那么
（3）其它情况下
那么在这道题的情况下，答案所求的是互异素数的乘积，利用容斥原理的思想我们可以发现：这与莫比乌斯函数恰巧是吻合的
首先二分答案（这里一开始我想错了，我一直在想二分选取质数的上界，然后怎么就搞不出来了。。）
首先有一个奇怪的证明是不会超过2n，并不会证，手推几个数果然是这样
二分MID以内有几个符合标准的数，然后答案为X-至少是一种质数平方的个数+至少是两种质数平方的个数……
因为当枚举的X不是互异素数的乘积是，mu[x]=0;否则，若K为奇数，则mu[x]=-1;else mu[x]=1;
这道题明显是懂了莫函数的“互异素数”之后才比较好想到 也可能是我太弱吧..
容斥功底不够..数学能力不够..多写题
#include<cstdio>
#include<algorithm>
#define M 44723
#define ll long long
using namespace std;
int tot,k;
,},pri[M],flag[M];
void Euler()
{
;i<=M;i++)
{
)mu[i]=-,pri[++tot]=i;
;j<=tot;j++)
{
if(pri[j]*i>M)break;
flag[pri[j]*i]=;
)
{
mu[pri[j]*i]=;break;
}
mu[pri[j]*i]=-mu[i];
}
}
}
int judge(int x)
{
;
;i*i<=x;i++)
re+=x/(i*i)*mu[i];
return re;
}
ll work()
{
ll l=,r=k<<;
<r)
{
ll mid=(l+r)>>;
if(judge(mid)>=k)r=mid;
else l=mid;
}
if(judge(l)>=k)return l;else return r;
}
int main()
{
int cas;scanf("%d",&cas);
Euler();
while(cas--)
{
scanf("%d",&k);
ll ans=work();
printf("%lld\n",ans);
}
}
07/23
bzoj3994
求n*m范围内的约数个数和。
蒟蒻不是很懂。。。。QAQ只会安利大爷们的题解