洛谷 P3327 [SDOI2015]约数个数和

传送门

颓颓颓推式子。

首先有一个玄学的式子：$d(ij)=\sum\limits_{a|i}\sum\limits_{b|j}[gcd(a,b)=1]$

然后就可以推了：（以下默认$n<m$）

$\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)$

$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i}\sum\limits_{e|j}[gcd(d,e)=1]$

$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i}\sum\limits_{e|j}\sum\limits_{a|gcd(d,e)}\mu(a)$

$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i}\sum\limits_{e|j}\sum\limits_{a|d,a|e}\mu(a)$

枚举$a,d,e$：

$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d=1}^n\sum\limits_{e=1}^m\sum\limits_{a=1}^n[d|i][e|j][a|d][a|e]\mu(a)$

$=\sum\limits_{a=1}^n\sum\limits_{d=1}^n\sum\limits_{i=1}^n[d|i]\sum\limits_{e=1}^m\sum\limits_{j=1}^m[e|j][a|d][a|e]\mu(a)$

$=\sum\limits_{a=1}^n\sum\limits_{d=1}^n\left\lfloor\dfrac{n}{d}\right\rfloor[a|d]\sum\limits_{e=1}^m\left\lfloor\dfrac{m}{e}\right\rfloor[a|e]\mu(a)$

$=\sum\limits_{a=1}^n\sum\limits_{d=1}^{\lfloor\frac{n}{a}\rfloor}\left\lfloor\dfrac{n}{ad}\right\rfloor\sum\limits_{e=1}^{\lfloor\frac{m}{a}\rfloor}\left\lfloor\dfrac{m}{ae}\right\rfloor\mu(a)$

设$f(n)=\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor$

现在我们求的就是$\sum\limits_{a=1}^nf(\left\lfloor\dfrac{n}{a}\right\rfloor)f(\left\lfloor\dfrac{m}{a}\right\rfloor)\mu(a)$

显然预处理出$f$就可以整除分块了。

$n$只有$50000$珂以暴力继续整除分块$O(n\sqrt{n})$预处理。

不过考虑这玩意的含义，就是约数个数前缀和。$O(n\log n)$筛出$d$就行了（懒得线筛了）

答案要开$long\ long$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 50005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int mu[maxn],prime[maxn>>2],sum[maxn],cnt;
bool is[maxn];
int main(){
    int t=read();
    mu[1]=is[1]=1;
    for(register int i=2;i<=50000;++i){
        if(!is[i])prime[++cnt]=i,mu[i]=-1;
        for(register int j=1;j<=cnt&&i*prime[j]<=50000;++j){
            is[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(register int i=1;i<=50000;++i)
        for(register int j=i;j<=50000;j+=i)
            ++sum[j];
    for(register int i=2;i<=50000;++i)mu[i]+=mu[i-1],sum[i]+=sum[i-1];
    while(t--){
        int n=read(),m=read();
        long long ans=0;
        if(n>m)swap(n,m);
        for(register int l=1,r;l<=n;l=r+1){
            r=min(n,min(n/(n/l),m/(m/l)));
            ans+=1ll*sum[n/l]*sum[m/l]*(mu[r]-mu[l-1]);
        }
        printf("%lld\n",ans);
    }
}