2023 Jiangsu Collegiate Programming Contest, 2023 National Invitational of CCPC (Hunan), The 13th Xiangtan Collegiate Programming Contest

https://codeforces.com/gym/104396

E. LCM Plus GCD

题意

给定 $x,k$，求满足条件的 $(a_1,a_2,\cdots,a_k)$ 的个数。

• $a_1,a_2,\cdots,a_k$ 各不相同。
• $\gcd(a_1,a_2,\cdots,a_k)+\mathrm{lcm}(a_1,a_2,\cdots,a_k)=x$。

结果对 $10^9+7$ 取模。

数据范围：$1\leq x,k\leq 10^9$。

题解

设 $\gcd(a_1,a_2,\cdots,a_k)=g$，记 $\mathrm{lcm}(a_1,a_2,\cdots,a_k)=a\times g$。则 $(1+a)\times g=x$。枚举 $g$，令 $a_i'=\dfrac{a_i}{g}$，则 $\gcd(a_1',a_2',\cdots,a_k')=1,\mathrm{lcm}(a_1',a_2',\cdots,a_k')=a$。对 $a$ 和 $a_i$ 做质因数分解，即 $a=\prod\limits_{j=1}^mp_j^{b_j},a_i=\prod\limits_{j=1}^mp_j^{c_{ij}}$。那么，每个 $c_{ij}$ 的取值一定在 $[0,b_j]$ 之间，同时，对每个 $p_j$ 有 $\min\{c_{ij}\}=0,\max\{c_{ij}\}=b_j$。我们考虑容斥，一共有 $2m$ 个约束，每个 $p_j$ 对应两个约束。一般地，每个 $p_j$ 有 $(1+b_j)$ 的贡献，但是如果它违反了一个约束，那么贡献要减少 $1$（因为 $0$ 或 $b_j$ 将无法取到），违反两个就减少 $2$。然后把每个 $p_j$ 的贡献相乘，就是总的取值可能，从中选 $k$ 个就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int p=1e9+7;
const int N=1e6+5;
int x,k;
ll fac[N],ifac[N];
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=i*fac[i-1]%p;
    ifac[0]=ifac[1]=1;
    for(int i=2;i<N;i++) ifac[i]=(p-p/i)*ifac[p%i]%p;
    for(int i=2;i<N;i++) ifac[i]=ifac[i]*ifac[i-1]%p;
}
ll C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*ifac[m]%p*ifac[n-m]%p;
}
ll solve(int g)
{
    int a=x/g-1;
    if(a==0) return 0;
    vector<pii> fac;
    for(int i=2;i*i<=a;i++)
        if(a%i==0)
        {
            int cnt=0;
            while(a%i==0)
            {
                cnt++;
                a/=i;
            }
            fac.push_back({i,cnt});
        }
    if(a>1) fac.push_back({a,1});
    int n=(int)fac.size();
    ll sum=0;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<n);j++)
        {
            int op=1,res=1;
            for(int k=0;k<n;k++)
            {
                int v=fac[k].second+1;
                if(i>>k&1)
                {
                    op*=-1;
                    v--;
                }
                if(j>>k&1)
                {
                    op*=-1;
                    v--;
                }
                res*=v;
            }
            sum=(sum+C(res,k)*op+p)%p;
        }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin>>x>>k;
    ll ans=0;
    for(int i=1;i*i<=x;i++)
        if(x%i==0)
        {
            ans=(ans+solve(i))%p;
            if(i*i!=x) ans=(ans+solve(x/i))%p;
        }
    cout<<ans<<'\n';
    return 0;
}