526互联

2023湘潭邀请赛 E（容斥）

发布时间 2023-05-31 19:08:31作者: 陌上&初安

题目跳转：E

题意：

输入 x, k，求大小为 k 的 不同 集合个数，其中所有数的 gcd + lcm = x。

思路：

E

AC代码：

// -----------------
#include <bits/stdc++.h>
#define xx first
#define yy second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define fixed fixed<<setprecision
#define endl '\n'
#define int long long
#define pb push_back
#define epb emplace_back
#define PII pair<int,int>

using namespace std;

int qmi(int a, int k, int p)
{ 
    int res = 1 % p;
    while (k)
    { 
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1; 
    }
    return res;
}
const int N1 = 1e6 + 10, mod = 1e9 + 7;

int fa[N1], infa[N1];
void initcp(int n)
{
    fa[0] = infa[0] = 1; 
    for (int i = 1; i < n; i ++ )
    {
        fa[i] = fa[i-1] * i % mod; 
        infa[i] = infa[i-1] * qmi(i, mod - 2, mod) % mod;
    }
}
int C(int a, int b)
{ 
    if(a < b) return 0; 
    return fa[a] * infa[a-b] % mod * infa[b] % mod;
}

const int N2 = 1e6 + 10;

int cntt, primes[N2], mob[N2];
bool stt[N2];
void initpr(int n)
{ 
    mob[1] = 1; for(int i = 2; i <= n; i ++)
    { 
        if(!stt[i]) primes[cntt ++] = i,mob[i] = -1;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            int t = primes[j] * i;
            stt[primes[j] * i] = true; 
            if (i % primes[j] == 0)
            {
                mob[t] = 0; 
                break; 
            } 
            mob[t] = mob[i] * (-1);
        }
    }
}

int x,k,ans;

void cal(int m)
{
    m -= 1;
    if(m == 0) return;
    // 分解质因子并存下来
    vector<PII> f;
    for(int i = 2; i * i <= m; i ++)
    {
        if(m % i) continue;
        int cnt = 0;
        while(m % i == 0) m /= i,cnt ++;
        f.epb(i,cnt);
    }
    if(m != 1) f.epb(m,1);
    
    // 根据不同的质因子枚举所有情况
    m = f.size();
    for(int i = 0; i < (1 << m); i ++)
    {
        for(int j = 0; j < (1 << m); j ++)
        {
            int res = 1, ff = 0;
            for(int k = 0; k < m; k ++)
            {
                int cc = f[k].yy + 1;
                if(i >> k & 1) ff ^= 1,cc --;
                if(j >> k & 1) ff ^= 1,cc --;
                res = res * max(0ll, cc);
            }
            // 容斥加减
            if(ff) ans = (ans - C(res, k) + mod) % mod;
            else ans = (ans + C(res, k)) % mod;
        }
    }
}

void solve()
{
    cin >> x >> k;
    // 计算x的因子的所有可能
    for(int i = 1; i * i <= x; i ++)
    {
        if(x % i) continue;
        cal(i);
        if(i * i != x) cal(x / i);
    }
    cout << (ans + mod) % mod  << endl;
}

signed main()
{
    IOS initcp(1000010); initpr(1000010);
    int T = 1;
    //cin >> T;
    while(T --) { solve(); }
    return 0;
}