M_sea

洛谷3327 [SDOI2015]约数个数和
LuoguBZOJ分析orz yyb有一个奇妙的式子:$\large d(ij)=\sum\limits_{x|i...
扫描右侧二维码阅读全文
26
2018/12

洛谷3327 [SDOI2015]约数个数和

Luogu

BZOJ

分析

orz yyb

有一个奇妙的式子:

$\large d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]$

然后就有:

$\large ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]$

把枚举因数丢到前面去:

$\large ans=\sum\limits_{x=1}^n\sum\limits_{y=1}^n\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{y}\right\rfloor[\gcd(x,y)=1]$

$\large ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1]$

$\large f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=x]$

$\large g(x)=\sum\limits_{x|d}f(d)$

就有

$\large g(d)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[d|\gcd(i,j)]$

显然$d|i$,$d|j$,所以设$i=xd,j=yd$,然后

$\large g(d)=\sum\limits_{x=1}^{n/d}\sum\limits_{y=1}^{m/d}\left\lfloor\frac{n}{xd}\right\rfloor\left\lfloor\frac{m}{yd}\right\rfloor$

$\large g(d)=\sum\limits_{x=1}^{n/d}\left\lfloor\frac{n/d}{x}\right\rfloor\cdot\sum\limits_{y=1}^{m/d}\left\lfloor\frac{m/d}{y}\right\rfloor$

$\large sum(n)=\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor$

然后还有一个奇妙的式子:

$\large sum(n)=\sum\limits_{i=1}^n d(i)$

然后你可以用线性筛筛$d(\,)$。

最后的答案:

$\large ans=f(1)=\sum\limits_{d=1}^n\mu(d)g(d)$

$\large ans=\sum\limits_{d=1}^n\mu(d)sum(\left\lfloor\frac{n}{d}\right\rfloor)sum(\left\lfloor\frac{m}{d}\right\rfloor)$

用线性筛筛出$\mu(\,)$和$d(\,)$,然后求前缀和,再数论分块一波即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=50000+10;

int mu[MAXN],d[MAXN],a[MAXN],v[MAXN];
int p[MAXN],tot;
inline void init(int n) {
    v[1]=mu[1]=d[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++tot]=i,mu[i]=-1,d[i]=2,a[i]=1;
        for (re int j=1;j<=tot&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i],d[i*p[j]]=d[i]*d[p[j]],a[i*p[j]]=1;
            else { mu[i*p[j]]=0,d[i*p[j]]=d[i]/(a[i]+1)*(a[i]+2),a[i*p[j]]=a[i]+1; break; }
        }
    }
    for (re int i=1;i<=n;++i) mu[i]+=mu[i-1],d[i]+=d[i-1];
}

inline long long calc(int n,int m) {
    if (n>m) swap(n,m);
    long long ans=0;
    for (re int l=1,r;l<=n;l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*d[n/l]*d[m/l]*(mu[r]-mu[l-1]);
    }
    return ans;
}

int main() {
    init(50001);
    int T=read();
    while (T--) {
        int n=read(),m=read();
        printf("%lld\n",calc(n,m));
    }
    return 0;
}
最后修改:2019 年 01 月 09 日 06 : 59 PM

发表评论