YY的GCD

2019-02-23

Ac链接

  • 题目描述:神犇YY虐完数论后给傻×kAc出了一题

    ​ 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对

    ​ kAc这种傻×必然不会了,于是向你来请教……

    ​ 多组输入(大概也就一万组吧……)

  • 解决本题需要了解莫比乌斯反演的知识,所以先来普及知识点(最为枯燥的部分,但忍下去)。

莫比乌斯函数

  • :莫比乌斯函数是啥啊?

    :(莫比乌斯是一个由容斥系数所构成的函数)。

  • μ(d)的定义:
    • 当d=1时,μ(d)=1;
    • 当d=\(\Pi_{i=1}^kp_i\)\(p_i\)为互质素数时,μ(d)=\((-1)^k\)。(说直白点,就是d分解质因数后,没有幂次大于平方的质因子,此时函数值根据分解的个数决定);
    • 只要当d含有任何质因子的幂大于等于2,则函数值为0。
  • 莫比乌斯函数的一些其他有趣的性质:
    • 对于任意正整数n,\(\sum_{d|n}μ(d)\)=[n=1]。(PS:这一条性质是莫比乌斯反演中最常用的)
    • 对于任意正整数n,\(\sum_{d|n} \frac{μ(d)}{d}\)=\(\frac{φ(n)}{n}\)。(这个性质很奇妙,把欧拉函数与莫比乌斯函数结合起来,下次学杜教筛会证明)。
  • 求莫比乌斯函数的程序实现不难,只需要在线性筛的程序上略作修改,便可以筛出μ函数。

void mu_get(){
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!v[i]){
            p[++m]=i,mu[i]=-1;
        }
        for(int j=1;j<=m;++j){
            if(p[j]>v[i]||i*p[j]>n) break;
            v[i*p[j]]=p[j];
            if(i%p[j]) break;
            else mu[i*p[j]]=-mu[i];
        }
    }
}

莫比乌斯反演

  • 解决了莫比乌斯函数的问题后,我们就迎来了恶心的莫比乌斯反演。

  • 莫比乌斯反演定理:F(n)和f(n)是定义在非负整数集合上的两个函数,并且满足条件:

    \[F(n)=\sum_{d|n}f(d)\]

    那么现在存在一个结论:

    \[f(n)=\sum_{d|n}μ(d)F(\frac{n}{d})\]

  • 莫比乌斯反演的证明主要有两种方式,其中一种就是通过定义来证明;另一种利用狄利克雷卷积。先来说一说第一种证明方法:

    \[\sum_{d|n}μ(d)F(\frac{n}{d})=\sum_{d|n}μ(d)\sum_{i|\frac{n}{d}}f(i)\]

    \[=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}μ(d)=f(n)\]

    (PS:如果不知道第二部如何推导第三部,可以考虑第二个式子枚举的i与d的关系,发现可以调换一下枚举的方式。如果不知道最后一步怎么来的,可以去看一下上面莫比乌斯函数的性质1)。
  • 当然,莫比乌斯反演有另外的一种形式,当F(n)和f(n)满足:

    \[F(n)=\sum_{n|d}f(d)\]

    可以推出:

    \[f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)\]

  • 感觉这个式子,可能在莫比乌斯反演中更加好用。

回到本题

  • 显然,Ans=\(\sum_{p\epsilon prim}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]\)

  • 对于这种和gcd有关的莫比乌斯反演,我们一般另f(d)为gcd(i,j)=d的个数,即f(d)=\(\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]\) 。那么F(n)为gcd(i,j)为n或者n的倍数的个数,即:

    \[F(n)=\sum_{n|d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{m}\rfloor\]

    那么根据莫比乌斯反演定理:

    \[f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)\]

  • 接下来就是化简式子了!

    \[Ans=\sum_{p\epsilon prim}f(p)\]

    \[=\sum_{p\epsilon prim}\sum_{p|d}μ(\frac{d}{p})F(d)\]

    换一个枚举项,枚举\(\lfloor\frac{d}{p}\rfloor\)

    \[\sum_{p\epsilon prim}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}μ(d)F(dp)=\sum_{p\epsilon prim}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}μ(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor\]

    这个dp看着很不爽,我们把它换成T

    \[Ans=\sum_{T=1}^{min(n,m)}\sum_{t|T,t\epsilon prim}μ(\frac{T}{t})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\]

    \[Ans=\sum_{T=1}^{min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{t|T,t\epsilon prim}μ(\frac{T}{t})\]

  • 这样就已经可以O(n)求了。不过这道题有多组数据,所以直接O(n)求会挂。所以我们利用前缀和的思路,打一个整除分块,就可以O(n)预处理,O(\(\sqrt{n}\))求每一组数据了。

历经磨难终于A掉了这道题,哎数学题推式子我总是看着题解一遍一遍推,还是没有感觉,弱啊……

Coding

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
int n,m,cnt,p[N],v[N],mu[N];ll sum[N],ans,g[N];
void get_mu(int a){
    mu[1]=1;
    for(int i=2;i<=a;++i){
        if(!v[i]){
            p[++cnt]=i;mu[i]=-1;
        }
        for(int j=1;j<=cnt;++j){
            if(p[j]*i>a) break;
            v[i*p[j]]=p[j];
            if(i%p[j]==0) break;
            else mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=cnt;++i){
        for(int j=1;j*p[i]<=a;++j) g[p[i]*j]+=mu[j];
    }
    for(int i=1;i<=a;++i) sum[i]=sum[i-1]+g[i];
}
int main(){
    get_mu(1e7);
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        ans=0;
        if(n>m) swap(n,m);
        for(int l=1,r;l<=n;l=r+1){
            r=min((n/(n/l)),m/(m/l));
            ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
感谢pengymdalao的精彩博客