分解质因数

题目

唐僧师徒一路西行，忽然狂风大作，烈焰冲天，四周温度骤然上升！沙僧低声道：“师父，妖气冲天，怕是红孩儿来了！”果然，前方火光四射，一个身穿红衣的孩童踏火而来，正是红孩儿！他大笑道：“想要活着过此地？必须先接下我的三昧真火试炼！”

话音未落，天空中浮现出n团炽热的火焰，每团火焰都有一个独立燃烧周期$a1,a2,…,an$，表示它们在经过该时间后会重新燃起，形成不灭的循环！红孩儿冷笑道：“这些火焰不会自行熄灭，只有找到一个它们共同的熄灭时刻，才能让它们同时熄灭！”

沙僧皱眉道：“这妖火威力无穷，若不及时熄灭，我们怕是难以抵挡。”

红孩儿继续冷笑道：“即便你算得出结果，还需要对998244353取模，否则火焰依旧不灭！”

沙僧擦了擦额头的汗：“小码哥，咱们的生死可全指望你了，快算算共同熄灭的时刻吧！”

格式

输入格式：

第一行一个整数$n(1≤n≤1e4)$。第二行n个整数$a1∼an(1≤ai≤1e9)$。

输出格式：

一行一个整数，表示答案。

样例 1

输入：

2
1 2

输出：

思路

两种思路。

基于质因数的最小公倍数求解

采用两两合并的形式，根据最小公倍数的性质可知：n个数的最小公倍数是这些数中每个数进行质因数分解后，所有的质因数按对应次数累乘的最终结果。

预处理，根据题目给的数据范围进行质数打表。本题题目范围是$1e9$，因此需要计算$sqrt(1e9)$范围内的质数。
根据质数表找检查每个数的质因数和其对应的次数
如果一个质因数在不同的数中都有分解出，则次数取高者
需要注意如果遍历完所有表内质数后，该数还有剩余，则它是一个在$sqrt(1e9)$范围外的质数，需要单独记录。
基于快速幂求质因数表的乘积和，注意取模。

基于取模性质的最小公倍数求解

采用两两合并的形式，根据模运算的性质和最小公倍数的性质可知：$LCM(a,b)\%mod=(a*b/gcd(a,b))\%mod$

整理得：$(a/gcd(a,b)\%mod)(b\%mod)\%mod$（或$(a\%mod)(b/gcd(a,b)\%mod)\%mod$）。

每录入一次数据合并一次即可。

模运算的性质

最小公倍数（LCM）性质

Code

基于质因数的最小公倍数求解

#include<iostream>
#include<unordered_map>

#define ll long long
using namespace std;

const int MOD = 998244353;
const int N = 1e4 + 5;
const int P = 31623;
int num[N] = { 0 };    //存题目数据
int pr[P + 5] = { 0 };     //31623内的质数表    
bool isP[P + 5] = { false };
ll n, res = 1;
unordered_map<int, int>tab;   //存质因数

void Pr() {
    int ind = 1;
    for (int i = 2;i < P;i++) {
        if (isP[i] == false) {
            pr[ind] = i;
            ind++;
            for (int j = i;j * i < P;j++) {
                isP[i * j] = true;
            }
        }
    }
}

void Prdp(int x) {
    for (int i = 1;i < P;i++) {
        if (pr[i] <= x && pr[i] != 0) {
            int y = 0;
            while (x % pr[i] == 0) {
                x /= pr[i];
                y++;
            }
            tab[pr[i]] = max(y, tab[pr[i]]);
        }
        if (x == 1||x==0)break;
    }
    if(x!=1||x!=0)tab[x]=1;
}

void FastPow(pair<int, int>x) {
    int k = x.first, v = x.second;
    ll temp = 1;
    while (v) {
        if (v & 1)temp = 1LL * k * temp % MOD;
        k = 1LL * k * k % MOD;
        v >>= 1;
    }
    res = temp * res % MOD;
}

int main()
{
    cin >> n;
    for (int i = 1;i <= n;i++)cin >> num[i];
    Pr();
    for (int i = 1;i <= n;i++)Prdp(num[i]);
    for (auto p : tab)FastPow(p);
    cout << res;
    return 0;
}