洛谷P3455/POI2007 ZAP-Queries

@Pelom  November 4, 2019

题意

求$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]$$

数据范围:$1 \le d \le a,b \le 50000$

题解

假设$a\le b$

$$ \begin{aligned} \sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k] &= \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{b}{k}\rfloor} [\gcd(i,j)=1] \\ &= \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{b}{k}\rfloor} \sum_{d|\gcd(i,j)} \mu(d) \\ &= \sum_{d=1}^{\lfloor\frac{a}{k}\rfloor} \mu(d) \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{b}{k}\rfloor} [d|\gcd(i,j)] \\ &= \sum_{d=1}^{\lfloor\frac{a}{k}\rfloor} \mu(d)\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor \end{aligned} $$

其中最后一步$$\sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{b}{k}\rfloor} [d|\gcd(i,j)]=\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$$是因为$$[d|\gcd(i,j)]=1$$仅当$i,j$同时为$d$的倍数
用数论分块计算$$\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$$
并用前缀和计算$$\mu(d)$$

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=50000;
int t,a,b,k;
int cnt;
LL ans;
int pri[N+1],mu[N+1],smu[N+1];
bool isp[N+1];
inline void sift(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!isp[i]){
            mu[i]=-1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt && i*pri[j]<=n;j++){
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)
                break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)
        smu[i]=smu[i-1]+mu[i];
}
inline LL calc(int a,int b){
    LL res=0;
    for(int l=1,r;l<=a;l=r+1){
        r=min(a/(a/l),b/(b/l));
        res+=1ll*(a/l)*(b/l)*(smu[r]-smu[l-1]);
    }
    return res;
}
int main(){
    scanf("%d",&t);
    sift(N);
    for(;t--;){
        scanf("%d%d%d",&a,&b,&k);
        if(a>b)
            swap(a,b);
        a/=k,b/=k;
        printf("%lld\n",calc(a,b));
    }
    return 0;
}

另一种推式子的方法:

设$$f(k)=\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]$$表示$\gcd(i,j)=k$的个数$$F(n)=\sum_{n|k}f(k)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor$$表示$\gcd(i,j)=k$的倍数的个数
莫比乌斯反演,有$$f(n)=\sum_{n|k} \mu(\lfloor\frac{k}{n}\rfloor)F(k)$$
将枚举$n$改为枚举$\lfloor\frac{k}{n}\rfloor$

$$ \begin{aligned} &= \sum_{d=1}^{\lfloor\frac{a}{k}\rfloor} \mu(d)F(kd) \\ &= \sum_{d=1}^{\lfloor\frac{a}{k}\rfloor} \mu(d)\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor \\ \end{aligned} $$


添加新评论