Bakser's Blog

我是逗比。

bzoj2820[YY的GCD]mobius反演

| Comments

又到了秀公式编辑器的时刻感谢ydc神犇的题解。

规定p为一个奇怪的质数,然后下面就是推倒

推到这一步就可以过掉bzoj1101了显然不是很科学,往下就进入奇怪的阶段了。

看上去没什么区别?这里悄悄的替换了求和变量,处理f的前缀和以后,我们只需要sqrt(n)的复杂度就可以分段统计答案了,就避免了枚举质数,所以问题在于快速统计f(x)。

bzoj2820
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MIN(a,b) (((a)<(b))?(a):(b))
const int N(1e7+1),hh[2]={1,-1};
typedef long long LL;
int T,n,m,g[N],h[N],prime[N],tot;
LL sum[N];
bool vis[N];
inline void sieve()
{
    for(int i(2);i<N;i++)
    {
        if(!vis[i])prime[tot++]=i,g[i]=h[i]=1;
        for(int j(0);j<tot&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            g[i*prime[j]]=g[i]+1;
            if(i%prime[j]==0)
            {
                h[i*prime[j]]=h[i];
                break;
            }
            else h[i*prime[j]]=h[i]+1;
        }
    }
    for(int i(2);i<N;i++)
    {
        int f;
        if(g[i]==h[i])f=hh[(h[i]-1)&1]*h[i];
        else if(g[i]-h[i]==1)f=hh[h[i]&1];
        else f=0;
        sum[i]=sum[i-1]+f;
    }
}
int main()
{
    scanf("%d",&T);
    sieve();
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        LL ans(0);int nxt;
        for(int i(1);i<=n;i=nxt+1)
        {
            int a(n/i),b(m/i);
            nxt=MIN(n/a,m/b);
            ans+=(sum[nxt]-sum[i-1])*a*b;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Comments

comments powered by Disqus