bzoj4816 [Sdoi2017]数字表格（反演）

题目链接

Description

分析：

∏i=1n∏j=1mf(gcd(i,j)) ∏ i = 1 n ∏ j = 1 m f ( g c d ( i , j ) )

对于这种式子，一般我们会枚举gcd（每个f值要使用几次）

设 g(d)=∑ni=1∑mj=1[gcd(i,j)=d] g ( d ) = ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ]

∏d=1min(n,m)f(d)g(d) ∏ d = 1 m i n ( n , m ) f ( d ) g ( d )

把 ∑ni=1∑mj=1[gcd(i,j)=d] ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] 用反演化开

g(d)=∑k=1min(n/d,m/d)nkdmkdμ(k) g ( d ) = ∑ k = 1 m i n ( n / d , m / d ) n k d m k d μ ( k )

∏d=1min(n,m)f(d)∑k=1nkdmkdμ(k) ∏ d = 1 m i n ( n , m ) f ( d ) ∑ k = 1 n k d m k d μ ( k )

像我这种naive的选手，到这里就直接做了

继续，我们看看 g(d) g ( d ) 能不能进一步优化，设 T=kd T = k d

g(d)=∑k=1min(n/d,m/d)nkdmkdμ(k)=∑d|TnTmTμ(Td) g ( d ) = ∑ k = 1 m i n ( n / d , m / d ) n k d m k d μ ( k ) = ∑ d | T n T m T μ ( T d )

这样我们就可把 T T 的枚举拉出来

∏d=1min(n,m)f(d)∑d|TnTmTμ(Td)∏d=1min(n,m)f(d)∑d|TnTmTμ(Td)

∏d=1min(n,m)∏d|Tf(d)nTmTμ(Td) ∏ d = 1 m i n ( n , m ) ∏ d | T f ( d ) n T m T μ ( T d )

枚举顺序换一下

∏T=1min(n,m)∏d|Tf(d)nTmTμ(Td)=∏T=1min(n,m)(∏d|Tf(d)μ(Td))nTmT ∏ T = 1 m i n ( n , m ) ∏ d | T f ( d ) n T m T μ ( T d ) = ∏ T = 1 m i n ( n , m ) ( ∏ d | T f ( d ) μ ( T d ) ) n T m T

发现对于每个 T T ，∏d|Tf(d)μ(Td)∏d|Tf(d)μ(Td)的值是固定的，与 n n 和mm无关，于是我们先用筛法预处理出每个 T T 对应的这个式子的值，前缀积一下

而外面这一层∏min(n,m)T=1()nTmT∏T=1min(n,m)()nTmT可以分块处理

所以时间复杂度： O((max(n,m)+T(n−−√+m−−√))logMOD) O ( ( m a x ( n , m ) + T ( n + m ) ) l o g M O D )

tip

∏d|Tf(d)μ(Td) ∏ d | T f ( d ) μ ( T d ) 直接暴力处理即可

设 sum s u m 为前缀积，注意 sum[0]=1 s u m [ 0 ] = 1

一开始预处理就慢到爆，怀疑人生

KSM次数多了也费时，所以我们预处理f的逆元，减少KSM的调用

因为要计算 f(d)μ(Td) f ( d ) μ ( T d ) ，而 μ μ <script type="math/tex" id="MathJax-Element-1569">μ</script>的取值只有-1，1，所以预处理f的逆元反而比较方便

多%防爆ll

还是免不了T掉了

ll改int，计算过程中强转ll

时间就少了一半诶

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

const int N=;
const ll p=e9+;
int sshu[N+],tot=,mu[N+],n,m;
int f[N+],sum[N+],inv[N+];
bool no[N+];

inline int KSM(int a,int b) {
    int t=;
    a%=p;
    while (b) {
        if (b&) t=(LL*t*a)%p;
        b>>=;
        a=(LL*a*a)%p;
    }
    return t%p;
}

void prepare() {    
    mu[]=;
    for (int i=;i<=N;i++) {
        if (!no[i]) {
            sshu[++tot]=i;
            mu[i]=-;
        }
        for (int j=;j<=tot&&sshu[j]*i<=N;j++) {
            no[sshu[j]*i]=;
            if (i%sshu[j]==) {
                mu[sshu[j]*i]=;
                break;
            }
            mu[sshu[j]*i]=-mu[i];
        }
    }

    f[]=; f[]=; 
    sum[]=; sum[]=;                               //前缀积
    inv[]=;                                         //f的逆元 
    for (int i=;i<=N;i++) f[i]=(f[i-]+f[i-])%p,inv[i]=KSM(f[i],p-),sum[i]=;
    for (int i=;i<=N;i++) 
        if (mu[i]!=) {
            for (int j=;j*i<=N;j++)                  // j*i=T i=T/d j=d
                if (mu[i]>) sum[j*i]=(LL*sum[j*i]*f[j])%p;
                else sum[j*i]=(LL*sum[j*i]*inv[j])%p;
        }
    for (int i=;i<=N;i++) sum[i]=(LL*sum[i]*sum[i-])%p; 
}

int main()
{
    prepare();
    int T;
    scanf("%d",&T);

    while (T--) {
        scanf("%d%d",&n,&m);
        int last,ans=;
        for (int i=;i<=min(n,m);i=last+) {
            last=min(n/(n/i),m/(m/i));
            ans=LL*ans%p*KSM(LL*sum[last]*KSM(sum[i-],p-)%p,LL*(n/i)*(m/i)%(p-))%p;
        }
        printf("%d\n",ans%p);
    }
    return ;
}