[BZOJ3309]DZY Loves Math 莫比乌斯反演+找规律


原题链接
一开始肯定是一些很套路的东西,推几步会变成(下取整好难打不打了)

前半部分直接分块就好了,接下来需要线性时间预处理后半部分,然后做一个前缀和.
设后半部分为,打表后发现:
当D所有质因子次数相同时,g(D)=(-1)^(k+1),其中k为质因子个数;
否则g(D)=0.
证明的话...考虑每个质因子的次数对答案的贡献吧,第一条简单,第二条略复杂.
然后就可以用线性筛求g了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10002333
using namespace std;
const int maxn=10000000;
typedef long long ll;
int n,m;
int v[N],prime[N>>2],cnt,minp[N],nump[N],pw[N],g[N];
//v:是否是质数 prime:质数表 cnt:质数个数
//minp:最小质因子 nump:最小质因子次数 pw:minp^nump g:目标函数
void drive()
{
    int i,j,k;
    for(i=2;i<=maxn;++i)
    {
        if(!v[i])
        {
            prime[++cnt]=i;
            minp[i]=i,nump[i]=1,pw[i]=i,g[i]=1;
        }
        for(j=1;j<=cnt&&(k=i*prime[j])<=maxn;++j)
        {
            v[k]=1;
            if(i%prime[j])
            {
                minp[k]=pw[k]=prime[j],nump[k]=1;
                if(nump[i]==1)g[k]=-g[i];
            }
            else
            {
                minp[k]=prime[j],pw[k]=pw[i]*prime[j],nump[k]=nump[i]+1;
                if(k==pw[k])g[k]=1;
                else if(nump[k]==nump[k/pw[k]])g[k]=-g[k/pw[k]];
                break;
            }
        }
    }
    for(i=2;i<=maxn;++i)g[i]+=g[i-1];
}
int T;
inline ll calc(int n,int m)
{
    if(n>m)swap(n,m);
    int i,last;ll re=0;
    for(i=1;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        re+=(ll)(n/i)*(m/i)*(g[last]-g[i-1]);
    }
    return re;
}
int main()
{
    drive();
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",calc(n,m));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注