ARC167 B

题面

Link

题意：给你两个数 $A,B$，问 $A^B$ 的所有因子的乘积能整除 $A$ 多少次？

• $2\leq A\leq 10^{12}$
• $0\leq B\leq 10^{18}$
• 所有输入都是整数

思路

首先把 $A$ 质因数分解，对于它的每个质因子 $p_i$ 和它们的指数 $k_i$ 之间互相组合便可以得到 $A$ 的所有因子。

我们假设要求得到所有因子的乘积后的数，设它质因数分解后每个质因子的指数为 $q_i$（底数和 $A$ 相同），那么：

$q_i=\dfrac{(k_i\times{b}+1)\times k_i\times{b}}{2}\times\prod_{j!=i}(k_j\times{b}+1)$

第一项表示这个指数自己有这么多种情况（其实就是 $\sum_{i=1}^{k_{i}b}i$），第二项表示它和其它指数组合会产生多少种情况（加一是因为其它指数取值范围为 $[0,k_i\times{b}]$）

化简一下就是：

\begin{gather} S=\prod_{i}(k_i\times{b}+1) \\ q_i=\dfrac{Sk_ib}{2} \end{gather}

答案就是 $\dfrac{q_i}{k_i}=\dfrac{Sb}{2}$

注意，这里假如 $k_i$ 是唯一的偶数，那么 $k_i$ 被除掉之后，剩下的就只有奇数了，所以有一个下取整的问题，注意我们想要的是先除后模。

判断一下分子是否有偶数因子即可，如果没有就 $-1$ 再模，由于是模意义下的除法所以要用逆元。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;

inline LL read()
{
    LL x = 0, y = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') y = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * y;
}
void put(LL x)
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
    if(x / 10) put(x / 10);
    putchar(x % 10 + '0');
}

LL ksm(LL x, int y)
{
    if(y == 0) return 1;
    LL z = ksm(x, y / 2);
    z = z * z % MOD;
    if(y & 1) z = z * x % MOD;
    return z;
}

LL a, b;
LL times[200006];
int cnt;

int main()
{
    a = read();
    b = read();
    for(int i = 2; 1ll * i * i <= a; i++)
    {
        if(a % i == 0)
        {
            cnt++;
            while(a % i == 0) a /= i, times[cnt]++;
        }
    }
    if(a != 1) times[++cnt] = 1;
    LL s = 1;
    bool bj = false;
    for(int i = 1; i <= cnt; i++)
    {
        if((b & 1) && (times[i] & 1)) bj = true;
        s = s * ((times[i] * (b % MOD) % MOD + 1) % MOD) % MOD;
    }
    if(b % 2 == 0) bj = true;
    s = s * (b % MOD) % MOD;
    if(bj == false) s = (s - 1 + MOD) % MOD, s = s * ksm(2, MOD - 2) % MOD;
    else s = s * ksm(2, MOD - 2) % MOD;
    put(s);
    return 0;
}