AtCoder Regular Contest 167——B - Product of Divisors

标签：AtCoder Product Contest int res flag 因子 ans

题目很明显，给定 所有因数的积不断除以最多能除几次。 首先，很容易发现，对于每一对因子，都可以对答案得出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

 

 

标签：AtCoder,Product,Contest,int,res,flag,因子,ans
From： https://www.cnblogs.com/sheppard23/p/17775744.html