又是一道神奇的题目。

一句话题意:给定 $n,m$ 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$

于是开始推式子:

有这么一条公式:

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

这个非常重要,至于证明的话,本人太弱,留个坑,到时候再填,请大家谅解 $QwQ$ 。

然后呢?发现题目求的式子后面正好是 $d(ij)$ ,于是美滋滋的套进去。

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

$x$ 和 $y$ 我们扔到前面去枚举,后面来计算它们对它们的倍数做出的贡献。

可以知道前面的 $x$ 在 $n$ 以内的倍数有 $\lfloor\frac{n}{x}\rfloor$ 个,$y$ 在 $m$ 以内的倍数有 $\lfloor\frac{m}{y}\rfloor$,于是:

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

$$=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=1]$$

按照套路,我们设:

$$f(x)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=k]$$

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

那么显然有:

$$g(k)=\sum_{k|d} f(d)$$

这个式子很有熟悉的味道,显然是反演常见的第二种形式。

所以就有:

$$f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)$$

我们的答案是 $f(1)$,那么就是:

$$f(1)=\sum_{d=1}^{n}\mu(d)g(d)$$

现在来考虑怎么计算 $g$ 。

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

后面的 $k$ 很碍眼,消掉他。

$$g(k)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor$$

于是我们预处理一个函数 $s$ :

$$s(k)=\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor$$

那么 $g(k)$ 就很好算了:

$$g(k)=s(n/k) \cdot s(m/k)$$

复杂度的话还好,预处理 $s$ 时可以整出分块,$O(\sqrt{n})$ 爽歪歪。然后的话,发现统计答案的时候 $g$ 函数也可以整出分块,$O(\sqrt{n})$ 。最后总时间复杂度 $O(T\sqrt{n})$ (???) 反正过了就行没超时,时间复杂度我也不会算 $QwQ$ 。

Code:

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

#define ll long long
#define min(x,y) ((x)<(y)?(x):(y))

const int N=5e4+2;
const int inf=1e9+9;

int T,n,m,cnt;
int mui[N],vis[N],prime[N];
ll s[N]; 

inline void _pre_mui(){
    mui[1]=1;
    for(int i=2;i<=N;++i){
        if(!vis[i])prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt;++j){
            if(i*prime[j]>5e4)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            mui[i*prime[j]]=-mui[i];
        }
    }
    for(int i=1;i<=N;++i)mui[i]+=mui[i-1];
    for(int x=1;x<=N;++x){//实际上这里是 O(n sqrt(n)),不过影响不大。
        ll res=0;
        for(int l=1,r=0;l<=x;l=r+1)
            r=(x/(x/l)),res+=1ll*(r-l+1)*(x/l);
        s[x]=res;
    }return;
}

inline ll solve(int n,int m){
    ll ans=0;
    if(n>m)n^=m^=n^=m;
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(mui[r]-mui[l-1])*s[n/l]*s[m/l];
    }return ans;
}

int main(){
    _pre_mui();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld\n",solve(n,m));
    }return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

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