P4450 双亲数题解

黑影洞人 · 2022-07-02 20:10:12 · 题解

提供一种超短的做法

我们设 f(d) 为 1≤a≤A,1≤b≤B 中 \gcd(a,b)=d 的二元组个数。

如何求 f(d) 成为本题的关键，我将用计数DP来解决。

我们打一个表观察一下 \gcd(a,b)。

1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 1 3 1 1 3 1 1 3 1
1 2 1 4 1 2 1 4 1 2
1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2
1 1 1 1 1 1 7 1 1 1
1 2 1 4 1 2 1 8 1 2
1 1 3 1 1 3 1 1 9 1
1 2 1 2 5 2 1 2 1 10

我们设函数 g(d) 是 \sum_{(a,b)}d| \gcd(a,b)。

如图，可以很直观的发现 g(d) 实际上就是 (A/d)*(B/d)。

我们可以很直观的发现，g(d)=f(d)+f(2d)+f(3d)……+f(\lfloor \frac{n}{d} \rfloor*d)。

于是我们反向推一下 f(d)=g(d)- f(2d)-f(3d)……-f(\lfloor \frac{n}{d} \rfloor*d) , 并且有边界条件 g(n)=f(n)=1。

于是我们就得到了 f(d) 的逆推式。

上代码：

#include<cstdio>
#include<algorithm>
#define int long long
#define N 100000006
using namespace std;
int k,g[N],f[N],ans,n,m,sum,Ch;
signed main(){
    scanf("%lld%lld%lld",&n,&m,&Ch);
    if(n>m)swap(n,m);
    for(int k=n;k>=1;k--){
        g[k]=(n/k)*(m/k);
        f[k]=g[k];
        for(int j=2;j<=(n/k);j++)f[k]-=f[j*k];
    }
    printf("%lld",f[Ch]);
    return 0;
}

算法时间复杂度为 O(nH(n))，其中 H(n) 为调和级数和，求一下积分可以知道时间复杂度约为 O(n \ln n)

P4450 双亲数 题解

P4450 双亲数题解