题目:
https://www.codechef.com/submit/MAKEIT1?tab=statement
题解:
https://www.codechef.com/submit/ROCKET_PACK?tab=solution
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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; }View Code
标签:cnt,质因数,return,res,LL,num,div,例题,DP From: https://www.cnblogs.com/ydUESTC/p/16625345.html