Luogu5106 dkw 的 lcm

题面

简化题意

给定 $n,k$，求：

$\prod_{i_1=1}^n \prod_{i_2=1}^n \cdots\prod_{i_k=1}^n \varphi(\rm{lcm}(i_1,i_2,\cdots,i_k))$

对 $10^9+7$ 取模。$n,k\leq 10^6$。

题解

不妨设集合 $S=\{i_1,i_2,\cdots,i_k\}$。下面我们类比 min-max 容斥给出一个式子：

对于任意积性函数 $f$，有：

$f(\rm{lcm}(x|x\in S)) = \prod_{T\subseteq S}f(\gcd(x|x\in T)^{(-1)^{\left|T\right|+1}})$

这个式子取 $f=\rm{id}$ 就有了朴素的 gcd-lcm 容斥。

将原式转化成这个形式：

$\prod_{S} \prod_{T\subseteq S} \varphi(\gcd(T))^{(-1)^{\left|T\right|+1}}$

枚举 $T$ 的大小：

$\prod_{j=1}^k \left( \prod_{i_1}^n \prod_{i_2}^n\cdots \prod_{i_j}^n \varphi(\gcd(i_1,i_2,\cdots,i_j)) \right)^{(-1)^{j+1}n^{k-j}\binom{k}{j}}$

括号里的一车东西是一个反演：

$\prod_{d=1}^n \varphi(d)^{\sum_{t=1}^{n/d} \mu(t)\left\lfloor\frac{n}{dt}\right\rfloor^k }$

这个东西可以考虑把指数拿下来：

$\prod_{t=1}^n \left( \prod_{d\mid t}\varphi(d)^{\mu(\frac{t}{d})} \right )^{\left\lfloor\frac{n}{t}\right\rfloor^k}$

括号里的东西可以写筛子预处理。将其记为 $f(t)$。回头代入原式整理一下可以得到：

$\prod_{t=1}^n f(t)^{-\sum_{j=1}^k \left\lfloor\frac{n}{t}\right\rfloor^j(-1)^jn^{k-j}\binom{k}{j}}$

指数的依托答辩是二项式定理，得到最终式：

$\prod_{t=1}^n f(t)^{n^k-(n-\left\lfloor\frac{n}{t}\right\rfloor)^k}$

可以 $n\log n$ 解决。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=1000006,mod=1000000007;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    if(p<0) return mi(mi(a),-p);
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}
inline int mi2(int a,int p){
    int mod=1000000006,res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

bool isp[max_n];
int cntp,pr[max_n/10],phi[max_n],mu[max_n];

int f[max_n],ivp[max_n];

inline void GetPr(int n){
    memset(isp,1,sizeof(isp)),isp[1]=0;
    phi[1]=mu[1]=1;
    for(register int i=2;i<=n;++i){
        if(isp[i]){
            pr[++cntp]=i;
            phi[i]=i-1,mu[i]=-1;
        }
        for(register int j=1;j<=cntp && i*pr[j]<=n;++j){
            isp[i*pr[j]]=0;
            if(i%pr[j]==0){
                phi[i*pr[j]]=phi[i]*pr[j],
                mu[i*pr[j]]=0;
                break;
            }
            phi[i*pr[j]]=phi[i]*phi[pr[j]],
            mu[i*pr[j]]=-mu[i];
        }
    }
    for(register int i=1;i<=n;++i)
        ivp[i]=mi(phi[i]);
    for(register int i=1;i<=n;++i)
        f[i]=1;
    for(register int i=1;i<=n;++i)
        for(register int j=i,k=1;j<=n;j+=i,++k) if(mu[k])
            f[j]=f[j]*(mu[k]==1?phi[i]:ivp[i])%mod;
}

int n,K,ans=1;

int pw[max_n];

signed main(){
    GetPr(1000000);
    n=read(),K=read();
    for(register int i=0;i<=n;++i)
        pw[i]=mi2(i,K);
    for(register int t=1;t<=n;++t)
        ans=ans*mi(f[t],pw[n]-pw[n-n/t])%mod;
    write(ans);
    return 0;
}