问题描述:

对于给定的整数$a,b,d$,有多少正整数对$x,y$,满足$x<=a,y<=b$并且$gcd(x,y)=d$

输入:

第一行包含一个正整数$n$,表示一共有$n$组数据$(1<=n<= 50000)$
接下来$n$行,每行表示一个询问。每行三个正整数,分别为$a,b,d$($1<=d<=a,b<=50000$)

输出:

对于每组询问,输出一个正整数,表示满足条件的整数对数

思路:

这是一个莫比乌斯反演的模版题,莫比乌斯反演虽然听起来很高级但内容还是比较好理解的。

首先是莫比乌斯函数$\mu(n)$,这是一个表示容斥系数的函数。它的定义是这样的:当n有相等的质因子$\mu(n)=0$;当n没有相等质因子且质因子个数为偶数$\mu(n)=1$;当$n$没有相等质因子且质因子个数为奇数$\mu(n)=-1$。

然后关于莫比乌斯反演有下面两个形式:我们设存在两个函数$F(n), f(n)$

形式一:如果满足条件$$F(n)=\sum_{d|n}f(d)$$
那么就有:$$f(n)=\sum_{d|n}\mu(d)F(\lfloor\frac{n}{d}\rfloor)$$
形式二:如果满足条件$$F(n)=\sum_{n|d}f(d)$$
那么就有:$$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$
关于证明,我这么菜自然是不懂的。

对于这道题,设$x=\lfloor a/d\rfloor$, $y=\lfloor b/d \rfloor$。显然可以将题目转化为求这样一个式子:
$$ans=\sum_{i=1}^{x} \sum_{j=1}^{y} [gcd(i, j)==1]$$
然后我们设$f(n)$为在范围内$gcd(i,j)=n$的的个数,设$F(n)$为在范围内$n|gcd(i,j)$的个数,因此 $$F(n)=\lfloor x/n\rfloor*\lfloor y/n\rfloor$$
那么很显然,函数$f(d),F(n)$满足反演的第二种形式且$f(1)$就是我们所求答案。于是利用反演得到:
$$f(1)=\sum_{d=1}^{min(x, y)}\mu(d)F(d)$$

于是直接计算就是这样的(实测70分):

for(int j=1; j<=min(a, b); j++) ans+=mob[j]*(a/j)*(b/j);
//注意这里的mob是未经前缀和处理的

然后可以发现$a/j, b/j$的取值是一段一段的,所以我们利用数论分块的方法进行优化。数论分块可以看这道题:BZOJ1257 余数之和,然后代码是这样的:

for(int l=1, r; l<=min(a, b); l=r+1)
{
    r=min(a/(a/l), b/(b/l));
    ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
}
//注意这里的mob是经过前缀和处理的

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define MAXN 500005
#define LL long long
using namespace std;

int n, a, b, d, cnt, pri[MAXN], tag[MAXN], mob[MAXN];

void init()
{
    mob[1]=1;
    for(int i=2; i<=50000; i++)
    {
        if(!tag[i]) pri[++cnt]=i, mob[i]=-1;
        for(int j=1; j<=cnt && pri[j]*i<=50000; j++)
        {
            tag[i*pri[j]]=1;
            if(i%pri[j]==0) {mob[i*pri[j]]=0; break;}
            else mob[i*pri[j]]=-mob[i];
        }
    }
    for(int i=2; i<=50000; i++) mob[i]+=mob[i-1];
}

int main()
{
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int ans=0;
        scanf("%d%d%d", &a, &b, &d);
        a/=d; b/=d;
        for(int l=1, r; l<=min(a, b); l=r+1)
        {
            r=min(a/(a/l), b/(b/l));
            ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
        }
        printf("%dn", ans);
    }
}

发表评论

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