质因数+树形DP例题

题目：

https://www.codechef.com/submit/MAKEIT1?tab=statement

题解：

https://www.codechef.com/submit/ROCKET_PACK?tab=solution

代码：

#include<bits/stdc++.h>
#include<unordered_set>
#define fore(x,y,z) for(LL x=(y);x<=(z);x++)
#define forn(x,y,z) for(LL x=(y);x<(z);x++)
#define rofe(x,y,z) for(LL x=(y);x>=(z);x--)
#define rofn(x,y,z) for(LL x=(y);x>(z);x--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

unordered_map<LL, unordered_map<LL, LL>> p_to_p;

LL MOD = 998244353;
LL dp[1000010];

unordered_set<LL> vis;
LL DP(LL num)
{
    
    if (dp[num]!=0)
        return dp[num];
    if (p_to_p.count(num) == 0)
    {
        dp[num] = 1;
        return 1;
    }
    LL res = 1;
    vis.insert(num);
    for (auto [nxt, cnt] : p_to_p[num])
    {
        if (vis.count(nxt))
            return -1;
        LL tmp = DP(nxt);
        if (tmp > 0)
        {
            res = (res + tmp * cnt % MOD) % MOD;
        }
        else
            return -1;
    }
    vis.erase(num);
    dp[num] = res;
    return res;

}
void YD()
{
    LL n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        LL a, b;
        cin >> a >> b;
        

        LL o = b;
        for (LL j = 2; j * j <= o; j++)
        {
            if (b % j == 0)
            {
                LL cnt = 0;

                while (b % j == 0)
                    b /= j, cnt++;
                p_to_p[a][j] += cnt;
                p_to_p[a][j] %= MOD;
            }
        }
        if (b != 1)
        {
            p_to_p[a][b] += 1;
            p_to_p[a][b] %= MOD;
        }


        

    }


    vector<LL> div;
    vector<LL> cnt;
    LL o = n;
    for (LL i = 2; i * i <= n; i++)
    {
        if (o % i == 0)
        {
            int c = 0;
            div.push_back(i);
            while (o % i == 0)
                o /= i, c++;
            c %= MOD;
            cnt.push_back(c);
        }
    }
    if (o != 1)
    {
        div.push_back(o);
        cnt.push_back(1);
    }

    unordered_map<LL, LL> div_cnt;
    for (int i = 0; i < div.size(); i++)
    {
        div_cnt[div[i]] = cnt[i];
    }

    LL res = 0;

    for (auto [aa, bb] : div_cnt)
    {
        vis.clear();
        LL num = DP(aa);
        if (num < 0)
        {
            cout << -1 << endl;
            return;
        }
        res += bb * num%MOD; 
        res %= MOD;
    }
        





    cout << res << endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        YD();
    }
    return 0;
}