Processing math: 100%

最近在其他地方写文章,为了证明我没咕,把最近写的转到 Mina 上来吧。

文章或许有纰漏,希望大神可以指出 QwQ 。那么进入正题吧。

很显然是让我们求出下式:

ans=Ai=1Bj=1[gcd(i,j)=K]

根据性质可以得到:

ans=AKi=1BKj=1[gcd(i,j)=1]

我们设两个函数:

  • 函数 ff(x) 表示 AKi=1BKj=1[gcd(i,j)=x]
  • 函数 gg(x) 表示 AKi=1BKj=1[x|gcd(i,j)]

我们可以得到:

g(x)=x|df(d)

这是莫比乌斯反演的第二个形式:

g(n)=n|df(d)  f(n)=n|dg(d)μ(dn)

于是:

g(x)=x|df(x)  f(x)=x|dg(x)μ(dx)

=g(x)=x|df(x)  f(x)=x|dg(dx)μ(x)

n=AK , m=BK

那么:

g(x)=ni=1mi=1[x|gcd(i,j)]=nKi=1mKj=1[1|gcd(i,j)]

=nKi=1mKj=1[1|gcd(i,j)]=AK×BK

ans=f(1)

f(1)=ni=1μ(i)g(i)=ni=1μ(i)AKBK

这个式子是 O(n) 的。

发现 AK×BK 可以整除分块,于是我们便可以做到 O(n)

Code:

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

const int N=1e5+2;
const int inf=1e9+9;

int T,cnt;
int prime[N],mui[N],vis[N];
long long sum[N];

inline int _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]>=N)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            else mui[i*prime[j]]=-mui[i];
        }
    }for(int i=1;i<=N;++i)sum[i]=sum[i-1]+mui[i];
    return 0;
}

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

inline void solve(int n,int m,int k){
    long long ans=0;
    n/=k,m/=k;
    int lim=min(n,m);
    for(int i=1;i<=lim;){
        long long j=min(n/(n/i),m/(m/i));
        ans+=1ll*(sum[j]-sum[i-1])*(n/i)*(m/i);n
        i=j+1;
    }printf("%lld\n",ans);
    return;
}

int main(){
    _Pre_mui();
    scanf("%d",&T);
    while(T--){
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        solve(n,m,k);
    }return 0;  
}
C++

所以就没了。

分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

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