CF1866B

题面

Link

On the trip to campus during the mid semester exam period, Chaneka thinks of two positive integers $X$ and $Y$. Since the two integers can be very big, both are represented using their prime factorisations, such that:

• $X=A_1^{B_1}\times A_2^{B_2}\times\ldots\times A_N^{B_N}$ (each $A_i$ is prime, each $B_i$ is positive, and $A_1<A_2<\ldots<A_N$)
• $Y=C_1^{D_1}\times C_2^{D_2}\times\ldots\times C_M^{D_M}$ (each $C_j$ is prime, each $D_j$ is positive, and $C_1<C_2<\ldots<C_M$)

Chaneka ponders about these two integers for too long throughout the trip, so Chaneka’s friend commands her “Gece, deh!” (move fast) in order to not be late for the exam.

Because of that command, Chaneka comes up with a problem, how many pairs of positive integers $p$ and $q$ such that $\operatorname{lcm}(p, q) = X$ and $\gcd(p, q) = Y$. Since the answer can be very big, output the answer modulo $998\,244\,353$.

Notes:

• $\operatorname{lcm}(p, q)$ is the smallest positive integer that is simultaneously divisible by $p$ and $q$.
• $\gcd(p, q)$ is the biggest positive integer that simultaneously divides $p$ and $q$.

思路

显然，$p$ 和 $q$ 的 $\gcd$ 和 $\operatorname{lcm}$ 满足如下性质：

设 $f_i(p)$ 表示 $p$ 中 $i$ 这个质因子的指数，$S$ 为 $p$ 和 $q$ 的质因子集合的并集。

$\gcd(p,q)$ 是 $p$ 和 $q$ 质因子的最小交集，即 $\forall i\in S,f_i(\gcd(p,q))=\min(f_i(p),f_i(q))$。

同理，$\forall i\in S,f_i(\operatorname{lcm}(p,q))=\max(f_i(p),f_i(q))$。

现在已知：$\operatorname{lcm}(p,q)=X,\gcd(p,q)=Y$，那么就有以下三种情况：

• $\exists i\in S,f_i(X)<f_i(X)$ 直接输出 0，因为不存在一组 $p,q$ 满足条件。
• $f_i(X)=f_i(Y)$，这个时候只有一种情况，即 $f_i(p)=f_i(q)=f_i(X)=f_i(Y)$。
• $f_i(X)>f_i(Y)$，这个时候有两种情况：
  • $f_i(p)=f_i(X),f_i(q)=f_i(Y)$
  • $f_i(p)=f_i(Y),f_i(q)=f_i(X)$

代码

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

map<int, int> s1, s2; // X Y 中对应的指数
set<int> s;
int n, m, ans = 1;
int a[N], b[N], c[N], d[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), s.insert(a[i]);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        s1[a[i]] = b[i];
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
        scanf("%d", &c[i]), s.insert(c[i]);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &d[i]);
        s2[c[i]] = d[i];
    }
    for(auto &i : s)
    {
        if(s1[i] < s2[i])
        {
            cout << 0 << endl;
            return 0;
        }
        else if(s1[i] == s2[i]) continue;
        else ans = ans * 2 % MOD;
    }
    cout << ans;
    return 0;
}