题意

有一个 $n$ 个点的图，有 $m$ 条有向边 $u \to v$，保证 $u < v$,每个点有一个 $c_i$。一开始每个点有一个点权 $a_i$。每次操作可以给 $1$ 号点的点权加上 $1$。如果一个点的 $a_i = c_i$，那么 $a_i \gets 0$，并且所有 $i$ 指向的点 $j$，都会 $a_j \gets a_j + 1$。求多少次之后所有 $a_i$ 会再一次全变成 $0$。答案模 $998244353$。

$1 \le n \le 10^4,1 \le m \le 3\times 10^3$

分析

容易发现，我们希望让一个数字变回 $0$，那么就一定要进行前面进行过的操作若干轮。即假设之前操作了 $x$，那么要使得 $a_i$ 变成 $0$ 的操作次数 $y$ 一定 $y | x$。

我们还发现，这张图一定是 DAG，并且 $1$ 到 $n$ 的序列一定是拓扑序之一。于是，我们从前向后考虑。假设操作了 $1$ 到 $i - 1$ 之后 $j$ 的点权变成了 $a_j$，那么我们就知道，想让 $i$ 也变成 $0$ 就一定要再进行若干轮之前的操作，不妨设为 $ans$。那么就会有 $ans \gets ans \times \frac{c_i}{gcd(a_i,c_i)}$。设 $mul = \frac{c_i}{gcd(a_i,c_i)}$，那么就是所有 $j \in [i,n]$ 都会 $a_j \gets a_j \times mul$。

接下来我们考虑走 DAG 推走。这个也是好做的，直接暴力枚举即可。

综上，时间复杂度是 $O(n^2 + nm)$ 的，看上去很悬，但是我最慢点只跑了 $500$ ms。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 10005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
il ll gcd(ll a, ll b){return (!b ? a : gcd(b, a % b));}
const int P = 998244353;
int n, m, u, v, c[N];
ll ans, a[N];
vector <int> e[N];
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) c[i] = rd();
    for (int i = 1; i <= m; i++) u = rd(), v = rd(), e[u].push_back(v);
    a[1] = ans = 1;
    for (int i = 1; i <= n; i++){
        int mul = c[i] / gcd(c[i], a[i]);
        ans = ans * mul % P;
        for (int j = i; j <= n; j++) a[j] *= mul;
        for (int j = i; j <= n; j++){
            for (int v : e[j]) a[v] += a[j] / c[j];
            a[j] %= c[j];
        }
    }
    printf ("%lld\n", ans);
    return 0;
}