P13732 【MGVOI R1-D】图上的数（graph）

· · 题解

由算术基本定理，令 n=\prod\limits_{i=1}^{k}p_i^{c_i}。

则 E(n)=\sum c_i，T(n)=\dfrac{E(n)!}{\prod_{i=1}^k c_i!}，A(n)=\dfrac{E(n)!}{T(n)}=\prod_{i=1}^k c_i!。

于是第一问可以在 \mathcal{O}(\sqrt{a}) 的时间内解决。

显然也可以通过预处理做到 \mathcal{O}(\sqrt{a}) - \mathcal{O}\left(\dfrac{\sqrt{a}}{\log{a}}\right)，但是没有必要。

对于第二问，考虑分别计数 \text{ans}_1=\sum\limits_{d|n}\sum\limits_{d|k|n}1，\text{ans}_2=\sum\limits_{d|n}d\cdot A(d)\cdot \sum\limits_{d|k|n}k，令 d=\prod\limits_{i=1}^{k}p_i^{h_i}。

接下来是非常简单的推式子。虽然看起来有一些恐怖。

\begin{aligned} \text{ans}_1 &= \sum_{d|n}\sum_{d|k|n}1 = \sum_{d|n}\prod_{i=1}^k(c_i-h_i+1)= \sum_{d|n}\prod_{i=1}^k(h_i+1) \\ &= \prod_{i=1}^k\sum_{i=0}^{c_i}(i+1)= \prod_{i=1}^k\dfrac{(c_i+1)(c_i+2)}{2} \\ \\\text{ans}_2 &=\sum_{d|n}d\cdot A(d)\cdot \sum_{d|k|n}k= \sum_{d|n} d^2 \cdot A(d) \cdot\sum_{k|\frac{n}{d}} k \\ &= \sum_{d|n}\prod_{i=1}^{k}\left(p_i^{2h_i}\cdot h_i!\cdot\sum_{j=0}^{c_i-h_i}p_i^j\right)\\&=\prod_{i=1}^{k}\sum_{j=0}^{c_i} p_i^{2j} \cdot j! \cdot \dfrac{p_i^{c_i-j+1}-1}{p_i-1}\end{aligned}

时间复杂度 \mathcal{O}(\sqrt{a}+b\log a)，空间复杂度 \mathcal{O}(\log a)。

:::success[【MGVOI R1-D】图上的数 - graph.cpp]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=20;
const int mod=1e9+7;
int cnt[maxn],p[maxn];
inline int qkpow(int a,int p){
    int res=1;
    while(p){
        if(p&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod,p>>=1;
    }
    return res;
}
inline int sol(int n,int m){
    ll res=0;
    int val=1,inv=qkpow(n-1,mod-2);
    int invn=qkpow(n,mod-2),pw=qkpow(n,m+1);
    for(int i=0;i<=m;i++){
        if(i){
            val=1ll*val*i%mod*n%mod*n%mod;
            pw=1ll*pw*invn%mod;
        }
        res+=1ll*val*(pw+mod-1)%mod*inv%mod;
    }
    res%=mod;
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;cin>>t;
    while(t--){
        int a,b,k=0;
        cin>>a>>b;
        int cura=a;
        for(int i=2;i<=sqrt(a);i++){
            if(a%i) continue;
            p[++k]=i,cnt[k]=0;
            while(a%i==0) cnt[k]+=b,a/=i;
        }
        if(a>1) p[++k]=a,cnt[k]=b;
        int ans0=1,ans1=1,ans2=1,ljd=qkpow(cura,b);
        ljd=1ll*ljd*ljd%mod;
        for(int i=1;i<=k;i++){
            for(int j=1;j<=cnt[i];j++) ans0=1ll*ans0*j%mod;
            ans1=1ll*ans1*sol(p[i],cnt[i])%mod;
            ans2=1ll*ans2*(1ll*(cnt[i]+1)*(cnt[i]+2)/2%mod)%mod;
        }
        ans1=(ans1+ljd-ans2);
        ans1=(ans1%mod+mod)%mod;
        cout<<ans0<<" "<<ans1<<"\n";
    }
    return 0;
}

:::