526互联

AtCoder Regular Contest 167——B - Product of Divisors

发布时间 2023-10-19 21:45:47作者: sheppard23

题目很明显，给定 所有因数的积不断除以最多能除几次。
首先，很容易发现，对于每一对因子，都可以对答案得出B的贡献，设A的因子数目为n。
将A进行质因数分解，PBa1,PBa2,PBa3……PBam，那么因数个数就是质因子加一的乘积。
那么因子对数也就是前者一半。答案就是B乘因子对数除以二注意此处除操作是下取整，需对结果进行奇偶判断，如果是另行奇数-1，然后分别乘二的逆元得出答案
int m = 998244353;
int qmid(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void solve()
{
    int a, b;
    cin >> a >> b;
    int ans = 1; 
    bool flag = b % 2 == 0;
    for (int i = 2; i * i <= a; i++)
    {
        if (a % i == 0)
        {
            int cnt = 0;
            while (a % i == 0)
                cnt++, a /= i;
            int t = (1 + b % m * cnt) % m;
            ans = ans * t % m;
            if (cnt & 1)
                flag = 1;
        }
    }
    if (a > 1)
    {
        int t = (1 + b) % m;
        ans = ans * t % m;
        flag = 1;
    }
    ans = ans * (b % m) % m;

    if (!flag)
        ans = (ans - 1 + m) % m;
    ans = ans * qmid(2, m - 2) % m;
    cout << ans << endl;
}
View Code