【组合数学+插板法】CF893E

清疚 2024-03-16 11:07 46阅读 0赞

[Problem - 893E - Codeforces][]

题意：

![9b8b18625f244323a91936f7d4464fcc.png][]

思路：

![cff992738f7b4a739f215388079f0455.png][]

关于插板法：

![161eef03107a4d0fa059720319950cf8.png][]

Code：

注意逆元要线性求

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=9e6+10;
    const int mod=1e9+7;
    
    int x,y;
    int Fac[mxn],Inv[mxn];
    
    int ksm(int a,int b,int mod){
        int res=1;
        while(b>0){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
    int C(int n,int m){
        return ((Fac[n]*Inv[m])%mod)*Inv[n-m]%mod;
    }
    void F_init(){
        Fac[0]=1;
        for(int i=1;i<mxn;i++) Fac[i]=(Fac[i-1]*i)%mod;
        Inv[mxn-1]=ksm(Fac[mxn-1],mod-2,mod);
        for(int i=mxn-2;i>=0;i--){
            Inv[i]=(Inv[i+1]*(i+1))%mod;
        }
    }
    void solve(){
        cin>>x>>y;
        int ans=1;
        for(int i=2;i<=x/i;i++){
            int s=0;
            while(x%i==0){
                x/=i;
                s++;
            }
            ans=ans*C(s+y-1,y-1)%mod;
        }
        if(x>1) ans=ans*y%mod;
        ans=ans*ksm(2,y-1,mod)%mod;
        cout<<ans%mod<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        F_init();
        while(__--)solve();return 0;
    }

[Problem - 893E - Codeforces]: https://codeforces.com/problemset/problem/893/E
[9b8b18625f244323a91936f7d4464fcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cb7093a1cae1455e85c678c0abd59bb9.png
[cff992738f7b4a739f215388079f0455.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c8cd3e32d3214e749f5d6af321b3d53d.png
[161eef03107a4d0fa059720319950cf8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/598ed9babf6345c68c2b7b67c6fcbc27.png