Untitled

mail@pastecode.io avatar
unknown
c_cpp
13 days ago
3.4 kB
1
Indexable
Never
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define endl '\n'
#define PB push_back
#define pii pair<int, int>
#define SZ(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ff first
#define ss second
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e18;
const int MOD = 998244353;

bool isprime[N];
vector<int> prime;
void sieve(int n){
    for(int i=2; i<=n; i++)
        isprime[i] = 1;
    for(int i=2; i<=n; i++){
        if(!isprime[i]) continue;
        prime.PB(i);
        for(int j=i*i; j<=n; j+=i)
            isprime[j] = 0;
    }
}

const int MXN = 2e5 + 5;
const double EPS = 1e-6;
struct Dinic{
  struct Edge{ int v;double f;int re; };
  int n,s,t,level[MXN];
  vector<Edge> E[MXN];
  void init(int _n, int _s, int _t){
    n = _n; s = _s; t = _t;
    for (int i=0; i<n; i++) E[i].clear();
  }
  void add_edge(int u, int v, double f){
    E[u].PB({v,f,SZ(E[v])});
    E[v].PB({u,0,SZ(E[u])-1});
  }
  bool BFS(){
    for (int i=0; i<n; i++) level[i] = -1;
    queue<int> que;
    que.push(s);
    level[s] = 0;
    while (!que.empty()){
      int u = que.front(); que.pop();
      for (auto it : E[u]){
        if (it.f > 1e-6 && level[it.v] == -1){
          level[it.v] = level[u]+1;
          que.push(it.v);
    } } }
    return level[t] != -1;
  }
  double DFS(int u, double nf){
    if (u == t) return nf;
    double res = 0.0;
    for (auto &it : E[u]){
      if (it.f > EPS && level[it.v] == level[u]+1){
        double tf = DFS(it.v, min(nf,it.f));
        res += tf; nf -= tf; it.f -= tf;
        E[it.v][it.re].f += tf;
        if (nf < EPS) return res;
    } }
    if (!res) level[u] = -1;
    return res;
  }
  double flow(double res=0){
    while ( BFS() )
      res += DFS(s,INF);
    return res;
} }flow;

int fpow(int x, int y){
    int ret = 1;
    while(y){
        if(y & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ret;
}
int inv(int x){ return fpow(x, MOD-2); }

void solve(){    
    const int MXN = 2000;
    sieve(MXN);

    map<int, int> idx;
    int sz = 1;
    for(auto p : prime){
        int x = p;
        while(x <= MXN){
            idx[x] = sz++;
            x *= p;
        }
    }

    int n; cin >> n;
    vector<int> b(n), t(n);
    for(int i=0; i<n; i++)
        cin >> b[i];
    for(int i=0; i<n; i++)
        cin >> t[i];
    
    int st = 0, ed = n+sz+1;
    flow.init(ed+1, st, ed);

    for(int i=0; i<n; i++)
        flow.add_edge(st, i+1, log(b[i]));
    for(int i=0; i<n; i++){
        int x = t[i];
        for(auto p : prime){
            int P = 1;
            while(x % p == 0){
                P *= p;
                x /= p;
            }
            if(P > 1){
                flow.add_edge(i+1, n+idx[P], INF);
            }
        }
    }

    for(auto p : prime){
        int x = p;
        while(x <= MXN){
            flow.add_edge(n+idx[x], ed, log(p));
            flow.add_edge(n+idx[x], n+idx[x/p], INF);
            x *= p;
        }
    }

    flow.flow();
    int x = 1, y = 1;
    for(int i=0; i<n; i++){
        if(flow.E[st][i].f > 0){
            x = x * b[i] % MOD;
            y = y * t[i] % MOD * inv(gcd(y, t[i])) % MOD;
        }
    }
    cout << x * inv(y) % MOD << endl;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
}
Leave a Comment